Great Ideas in Theoretical Computer Science

Theory Lunch Edition!

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. If you have any suggestions for future discussions, please contact g@csail.mit.edu.

This page is for historical purposes - for the current Theory Lunch website, please go here.

Fall 2013 Discussions

• October 9, Some Problems on Shared Memory, presented by Rati Gelashvili
• October 2, Alternative Models of Quantum Computation, presented by Adam Bouland
• September 25, the Facility Location Problem, presented by Christos Tzamos
• September 16, Diverse Nearest Neighbor, presented by Sepideh Mahabadi
• September 10, SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge, presented by Madars Virza

Summer 2013 Discussions

• July 16, Local Graph Algorithms, presented by Themis Gouleakis
• July 2, Oriented Percolation on Grids, presented by Emily Berger
• June 25, Testing properties of distributions: comparing query models, presented by Clément Canonne
• June 18, Parity and Simple Stochastic Games, presented by Andrey Grinshpun

Spring 2013 Discussions

• May 21, Permutation Groups and the Schreier-Sims algorithm, presented by Zachary Abel
• May 14, finding disease clusters using Euclidean MSTs, presented by Sean Simmons
• May 7, Online Learning Frameworks: Mistake Bound, KWIK, and their mixture, presented by Morteza Zadimoghaddam
• April 30, how to solve Max Flow using numerical analysis, presented by Yin Tat Lee
• April 23, the firing squad problem, presented by Justin Kopinsky
• April 16, sampling from max entropy distributions, presented by Adrian Vladu
• April 9, fun time with entropy, presented by Henry Yuen
• March 12, matrix completions, presented by Alex Levin
• March 5, short lists for shorter programs in short time, presented by Michael Forbes
• February 26, the Constrained Earth Mover Distance model and applications to Compressive Sensing, presented by Ludwig Schmidt
• February 19, connection between 1-query static membership data structures and RIP-matrices, presented by Ilya Razenshteyn

Fall 2012 Discussions

• December 11, variants of Hilbert's Tenth Problem, presented by Shalev Ben-David
• December 4, affine-invariant codes, presented by Alan Guo
• November 27, some problems on the boolean hypercube, presented by Mohammad Bavarian
• November 20, a connection between online ski rental and vertex cover via bipartite matching, presented by Sam Wong
• November 13, STOC submission summaries, presented by Elette Boyle, Elad Haramaty, Eric Price, and Aaron Sidford
• November 6, Renaming in distributed computing, presented by Dan Alistarh
• October 23, an interesting property of a classic identity, presented by Gautam Kamath
• October 16, the Tree Augmentation Problem, presented by Elyot Grant