Theory of Computing Reading Seminar
Spring 2016


Michael Saks and Sijian Tang


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.


Jan 20th Core 433 Sijian Tang Benjamin Rossman, The Average Sensitivity of Bounded-Depth Formulas, FOCS 2015.
Jan 27th Core 433 Eric Allender Shuichi Hirahara, Osamu Watanabe, Limits of Minimum Circuit Size Problem as Oracle.
Feb 3rd Core 431 Amey Bhangale Sanjeev Arora, Boaz Barak, David Steurer, Subexponential Algorithms for Unique Games and Related Problems.
Feb 10th Core 433 Abhishek Bhrushundi Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Algorithms from Natural Lower Bounds.
Feb 17th Core 433 Abhishek Bhrushundi Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Algorithms from Natural Lower Bounds.

Possible future papers

Amir Abboud, Greg Bodwin, The 4/3 Additive Spanner Exponent is Tight.
Daniel Lokshtanov, Jesper Nederlof, Saving Space by Algebraization.
Martin Grohe, Pascal Schweitzer, Computing with Tangles, STOC 2015.
Artur Czumaj, Pan Peng, Christian Sohler, Testing Cluster structure of Graphs, STOC 2015.
Michael Elkin, Arnold Filtser, Ofer Neiman, Prioritized Metric Structures and Embedding, STOC 2015.
Jean Bourgain, Sjoerd Dirksen, Jelani Nelson, Toward a unified theory of sparse dimensionality reduction in Euclidean space, STOC 2015.
Sarah R. Allen, Ryan O'Donnell, David Witmer, How to refute a random CSP, FOCS 2015.
Yin Tat Lee, He Sun, Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time, FOCS 2015.
Stephen Alstrup, Soren Dahlgaard, Mathias Baek Tejs Knudsen, Optimal induced universal graphs and adjacency labeling for trees, FOCS 2015.
Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz, Solving the Closest Vector Problem in 2^n Time: The Discrete Gaussian Strikes Again!, FOCS 2015.
Lee-Ad Gottlieb, A light metric spanner, FOCS 2015.
Raghu Meka, Explicit resilient functions matching Ajtai-Linial.
Alexander Sherstov, The Power of Asymmetry in Constant-Depth Circuits, FOCS 2015.
Tsvi Kopelowitz, Ely Porat, Breaking the Variance: Approximating the Hamming Distance in O~(1/\epsilon) Time Per Alignment, FOCS 2015.

HTML 4.01 Strict