Michael Saks and Neil Lutz
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 here.
|January 25||CoRE 433||Neil||Mark Braverman and Omri Weinstein, A discrepancy lower bound for information complexity, ECCC 2011.|
|February 1||CoRE 433||Neil||Continued discussion of the paper from the previous week.|
|February 8||CoRE 433||Justin||Piotr Indyk, Reut Levi, and Ronitt Rubinfeld, Approximating and Testing k-Histogram Distributions in Sub-linear time, ECCC 2011.|
|February 15||CoRE 433||Edinah||Oded Goldreich and Salil Vadhan, On the complexity of computational problems regarding distributions (a survey), ECCC 2011.|
|February 22||CoRE 433||Luke||Valentine Kabanets and Osamu Watanabe, Is the Valiant-Vazirani Isolation Lemma Improvable?, ECCC 2011.|
|February 29||CoRE 433||Luke||Continued discussion of the paper from the previous week.|
|March 7||CoRE 433||Swastik||Daniel M. Kane, Small Designs for Path Connected Spaces and Path Connected Homogeneous Spaces, arXiv.org 2011.|
|March 14||-||-||No meeting|
|March 21||CoRE 433||Tim||Alexander A. Sherstov, The Multiparty Communication Complexity of Set Disjointness, ECCC 2011.|
|March 28||CoRE 433||Tim||Continued discussion of the paper from the previous week.|
|April 4||CoRE 433||Yixin||Klim Efremenko, From Irreducible Representations to Locally Decodable Codes, ECCC 2011.|
|April 11||CoRE 433||Yixin||Continued discussion of the paper from the previous week.|
|April 18||CoRE 433||Neil||Ada, Chattopadhyay, Cook, Fontes, Koucky, and Pitassi, The Hardness of Being Private, CCC 2012.|
|April 25||CoRE 433||Neil,
|Continued discussion of the paper from the previous week, and began:
Shachar Lovett, Raghu Meka, Constructive Discrepancy Minimization by Walking on The Edges, arXiv.org 2012.
|May 2||CoRE 433||Alantha||Continued discussion of the paper from the previous week|
|May 9||CoRE 433||Alex||Ben-Sasson, Lovett, and Zewi, An additive combinatorics approach to the log-rank conjecture in communication complexity, ECCC 2011.|
|May 16||CoRE 433||Alex||Continued discussion of the paper from the previous week|
|Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, and Phuong Nguyen, The NOF Multiparty Communication Complexity of Composed Functions, ECCC 2011.|
|Emanuele Viola, The communication complexity of addition, ECCC 2011.|
|Anna Gal, Michal Koucky, Pavel Pudlak, and Emanuele Viola, Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates, ECCC 2011.|
|A. Ta-Shma and C. Umans, Better condensers and new extractors from Parvaresh-Vardy codes, Manuscript, December 2011. To appear in CCC 2012.|