Great Ideas in Theoretical Computer Science — Theory Lunch Edition!
Organizers: Pritish Kamath (
), Jerry Li (
)
This page is only for historical purposes. For the current Theory Lunch website, please go here.
If you are not on the mailing list, sign up here!
Where: G5 Lounge (Stata Center)
When: Tuesdays at 12:45 PM (mostly so, but subject to change)
Theoretical Computer Science is full of great ideas, so once a week, the MIT Theory group gets together to socialize and share some knowledge. We'll briefly share some interesting ideas, and discuss a superset of these ideas over lunch.
Add this calendar to yours to receive details about upcoming events in the Theory group
(includes A&C Seminars, TOC Colloquium, CIS Seminars, Theory Lunch, TOC tea and more!) :
Click on the events above to get more description about the same (title/abstract for talks, etc.)
If you have any suggestions for future discussions, please contact and/or .
Fall 2014
October 8 : Agreement in partitioned dynamic networks - by Adam Sealfon
September 30 : Unique Games Conjecture and Optimality of Semi-definite programming - by Alex Wein
September 23 : Beyond Berry-Esseen: Structure and Learning Sums of Random Variables - by Gautam Kamath
September 16 : Graph connectivity under random sampling - by Mohsen Ghaffari
September 9 : Uniformity and bounded rank - by Ilya Razenshteyn
September 3 : General organizational meeting and discussions (no talk)
Summer 2014
August 27 : Stable instances of graph-partitioning problems - by Andreea Gane
August 20 : Compressive Sensing with Structured Sparsity - by Ludwig Schmidt
August 13 : Introduction to Compressed Sensing - by Jelena Markovic
August 4 : Recent developments in Program Obfuscation - by Prabhanjan Ananth
July 28 : Randomized Encodings - by Prashant Vasudevan
July 23 : Alternating Minimization for Matrix Completion - by Mădălina Persu
July 14 : Introduction to Sum-of-Squares hierarchy - by Jerry Li
July 7 : Introduction to Differential Privacy - by Adam Sealfon
June 30 : Set Cover in semi-streaming model - by Ali Vakilian
June 23 : Dimensionality Reduction for k-means clustering - by Christopher Musco
June 16 : Sparse recovery based sketching techniques and applications - by Cameron Musco
June 9 : A Physically Universal Cellular Automaton - by Luke Schaeffer
Spring 2014
May 26 : A computable nearly universal barrier function for polyhedral sets - by Yin-Tat Lee
May 19 : Better embeddings for planar Earth-Mover Distance over sparse sets - by Arturs Backurs
May 12 : The “trial and error” model of computation - by Adam Bouland
May 7 : Gaussian Mixture Models and Duelling Distributions and Robust Statistics! Oh My! - by Gautam Kamath
April 30 : Cryptographically Blinded Games: achieving coarse correlated equilibria by cheap talk - by Sunoo Park
April 23 : Tight bounds on entropy of almost pair-wise independent random variables - by Themistoklis Gouleakis
April 14 : Key-homomorphic pseudo-random functions - by Sergey Gorbunov
April 7 : Scheduling algorithms with applications to daily life - by Sam Elder
March 31 : Non-interactive simulation - by Sudeep Kamath
March 24 : Message-optimal leader election - by Rati Gelashvili
March 17 : An introduction to Program Obfuscation - by Aloni Cohen
March 10 : The Dichotomy of Constraint Satisfaction Problems - by Pritish Kamath
March 3 : The Lasserre Hierarchy - by Alex Wein
February 24 : An introduction to Combinatorial Game Theory - by Daniel Grier
February 20 : Convex optimization tools for obtaining approximate max-flow in nearly linear time - by Aaron Sidford
February 12 : The Busemann-Petty Problem - by Ilya Razenshteyn
February 5 : The Spraylist : A Scalable Relaxed Priority Queue - by Justin Kopinsky
January 29 : Linear Time Universal Steganography - by Justin Holmgren
January 22 : On a randomized version of Fibonacci heaps - by John Peebles
Fall 2013
December 11 : Making games harder using parallel repetition - by Henry Yuen
December 4 : A Vignette of Polynomial Identity Testing - by Michael Forbes
November 27 : Lower bounds for Branching Programs for Database Queries - by Jerry Li
November 20 : FPT Algorithm for Efficient Multistate Perfect Phylogeny - by Michael Coulombe
November 13 : Cilk-style parallelism - by William Leiserson
November 6 : Cache-oblivious algorithms - by Jayson Lynch
October 30 : A simple topological argument for finding the chromatic number of Kneser graphs - by Ilya Razenshteyn
October 23 : Research Introductions - by Mira Radeeva, Adam Bouland, Alex Dubbs, Ali Vakilian, Mohammad Bavarian and Matt Weinberg