Michael Saks and Justin Gilmer
The theory reading group meets weekly to discuss current papers in the theory of computing literature. Each week a volunteer leads us in reading a paper. The seminar is open to any interested participant.
A list of possible papers for presentation is given below. Suggested additions to the list can be made to the organizers.
It is expected (but not required) that each participant will serve as leader for at least one paper during the term. Participants who are new to theory of computing may attend for awhile before leading a paper.
Participants should bring their own copy (or e-copy) of the paper to the meeting. It is recommended, but not required, that participants read at least the introduction to the paper before the meeting.
The lead reader is expected to thoroughly read the paper in advance, but may not understand all of the details. He or she will lead us through the paper with some combination of a standard whiteboard presentation and group discussion of difficult points. Constructive interruptions, questions, etc. are encouraged.
When an interesting and (as far as we know) open problem arises during the discussion, the lead reader should make a note of it. These problems will be posted.
| DATE | LOCATION | LEADER | TOPIC |
|---|---|---|---|
| Aug 29th | Hill 705 | Group Reading | Zvika Brakerski, Yael Tauman Kalai, Efficient Interactive Coding Against Adversarial Noise, ECCC 2012. |
| Sept 12th | Core 433 | David Cash | Oded Goldreich, Rafail Ostrovsky, Software Protection and Simulation on Oblivious RAMs, J. ACM 43(3): 431-473 (1996). |
| Sept 19th | Core 433 | David Cash | Oded Goldreich, Rafail Ostrovsky, Software Protection and Simulation on Oblivious RAMs, J. ACM 43(3): 431-473 (1996). |
| Sept 26th | Core 433 | Swastik | Kasper Green Larsen, Higher Cell Probe Lower Bounds for Evaluating Polynomials, FOCS 2012. |
| Oct 3rd | Core 433 | Justin | Gregory Valiant, Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise, FOCS 2012. |
| Oct 10th | Core 433 | Raghu | Gabor Braun, Samuel Fiorini, Sebastian Pokutta, and David Steurer, Approximation Limits of Linear Program (Beyond Hierarchies), FOCS 2012. |
| Oct 17th | Core 433 | Yi Xin | Noga Alon, Amir Shpilka, Chris Umans , On Sunflowers and Matrix Multiplication, ECCC 2012. |
| Oct 24/31 | Core 433 | Hurricane Sandy | "On the destructive powers of hurricanes" |
| Nov 7/14th | Core 433 | Edinah | Shayan Oveis Gharan, Luca Trevisan , Approximating the Expansion Profile and Almost Optimal Local Graph Clustering, Arxiv 2012. |
| Nov 28th | Core 433 | Mrinal | Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi, Approaching the chasm at depth four, ECCC 2012. |
| Dec 5th | Core 433 | Alex | Cygan, Gabow, and Sankowski, Algorithmic Applications of Baur-Strassen's Theorem" by Cygan, Gabow, and Sankowski, Arxiv 2012. |
| Gregory Valiant, Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise , ECCC 2012. |
| Alexandre Benoit, Alin Bostan, and Joris van der Hoeven, Quasi-optimal multiplication of linear differential operators, FOCS 2012. |
| Taisuke Izumi and Tadashi Wadayama, A New Direction for Counting Perfect Matchings, FOCS 2012. |
| Marek Cygan, Harold N. Gabow, and Piotr Sankowski, Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, Diameter and Matchings, FOCS 2012. |
| Shayan Oveis Gharan and Luca Trevisan, Approximating the Expansion Profile and Almost Optimal Local Graph Clustering, FOCS 2012. |
| Andrew Drucker, New Limits to Classical and Quantum Instance Compression, FOCS 2012. |
| Kasper Green Larsen, Higher Cell Probe Lower Bounds for Evaluating Polynomials, FOCS 2012 |
| Nisheeth K. Vishnoi, A Permanent Approach to the Traveling Salesman Problem (link needed), FOCS 2012. |