Theory of Computing Reading Seminar
Spring 2012

The seminar page for summer 2012 is here

ORGANIZERS

Michael Saks and Neil Lutz

DESCRIPTION

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.

Meetings

DATE LOCATION LEADER TOPIC
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,
Alantha
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

Possible future papers

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.

HTML 4.01 Strict