MIT Complexity Student Reading Group

This is intended to be a focused reading group on current research topics in computational complexity. The group will jointly select a paper of common interest each week, and after reading the paper the members will meet to discuss the paper and understand it better. In addition, one member will volunteer to be responsible for the paper and lead the discussion.

Meeting at Mondays at 4PM in 32-G631 (the conference room).

Current topic:

hardness amplification

Past topics: Worst case versus average case; hardness versus randomness tradeoffs in "high" classes (e.g., NP, AM, etc.)

Date Leader Paper
5/12 Shubhangi Trevisan. List-decoding Using the XOR Lemma. FOCS 2003. (link, ECCC version)
5/5 Swastik Trevisan. On Uniform Amplification of Hardness in NP. STOC 2005. (link)
4/25 (Patriot's Day) Andy Bogdanov and Trevisan. On Worst-case to Average-case Reductions for NP Problems. FOCS 2003. (link)
4/15 @ 4pm in G531 (no TOC Colloquium) Vinod Bogdanov and Trevisan. Average-Case Complexity. (Ch. 7) (arXiv) (other links below)
4/8 @ 5:30pm
4/7 (RANDOM deadline + A&C conflict)
Brendan Kabanets. Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. Journal of Computer and System Sceinces 63:236-252, 2001. (link)
3/17 Danny Gutfreund, Shaltiel, and Ta-Shma. Uniform Hardness Versus Randomness Tradeoffs for Arthur-Merlin Games. Computational Complexity 12:85-130, 2003. (link)
3/10 Andy Kabanets and Impagliazzo. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13:1-46, 2004. (link)
3/3 (due to A&C seminar conflict)
2/25 (on account of President's day)
Swastik Miltersen and Vinodchandran. Derandomizing Arthur-Merlin Games using Hitting Sets, in Proc. 40th FOCS, 1999. (link)
(Journal version: Computational Complexity 14(3):256-279, 2005. link)

References from Chapter 7 of Bogdanov and Trevisan:

Other nominated topics:

Past terms

Fall Term 2007-2008 (topics: algorithms, cryptography, complexity; organizers: Nick Harvey, Brendan Juba)

The purpose of this group is to promote familiarity with fundamental or "classic" results, especially those that are often omitted from courses. We hope that participants will eventually volunteer to give a talk on a topic of general interest to the group. This term, we will encourage talks on Algorithms in addition to Foundational Cryptography and Complexity Theory.

Date Speaker Title (or topic)
9/14/07 Paul Valiant (cancelled) PPAD-completeness of finding Nash Equilibria in two-player games
9/21/07 (no speaker)
9/28/07 Brendan Juba Nisan's pseudorandom generator for space-bounded computation
10/5/07 (no speaker)
10/12/07 (no speaker)
10/19/07 Nick Harvey (cancelled due to Assaf Naor's talk)
10/26/07 Tasos Sidiropoulos Upper and Lower Bounds for Embedding into Constant-Dimensional Spaces
11/2/07 Vinod Vaikuntanathan Worst-case to Average-case Reductions for Lattice Problems (will start at 4:00pm)
11/9/07 Nick Harvey Hyperbolic Polynomials and Van der Waerden's Conjecture on Permanents (this talk and all future talks will start at 4:00pm)
11/16/07 Shubhangi Saraf New rounding techniques for semi-definite programs
11/23/07 (Thanksgiving break, no speaker)
11/30/07 Yury Lifshits Open Problems "To Go" (slides available:
12/7/07 Swastik Kopparty The Zig-zag product and Extreme Expanders

Spring Term 2006-2007 (topics: cryptography, complexity; organizers: Brendan Juba, Guy Rothblum)

Date Speaker Title (or topic)
2/9/07 Brendan Juba Characterizations of low-degree polynomials
2/16/07 Brendan Juba An efficient proof system for NEXP
2/23/07 Mihai Patrascu Information Complexity and High-dimensional Geometry
3/2/07 Adriana Lopez The Weil Pairing and Its Cryptographic Applications
3/9/07 Paul Valiant Computationally Sound Proofs
3/16/07 Bhavana Kanukurthi Private simultaneous message protocols and Randomizing polynomials
3/23/07 (Spring vacation, no speaker)
3/30/07 (Spring vacation, no speaker)
4/6/07 Benjamin Rossman Choiceless Polynomial Time
4/13/07 Nick Harvey The PCP theorem by gap amplification (will start at 3:30pm)
4/20/07 (FOCS deadline, no speaker)
4/27/07 Swastik Kopparty Error-correcting codes and Fourier Analysis
5/4/07 Jelani Nelson Algorithms for random 3SAT
5/11/07 (Ron 60 Fest, no speaker)

Fall Term 2006-2007 (topics: cryptography, complexity; organizers: Brendan Juba, Guy Rothblum)

Date Speaker Title
9/15/06 Swastik Kopparty Some modern day extractors and pseudorandom generators
9/29/06 Vinod Vaikuntanathan Simulating BPP Algorithms with Imperfect Randomness
10/13/06 Guy Rothblum Cryptography in NC0
10/20/06 Alex Andoni Fourier Analysis and proving non-embeddability into l_1
10/27/06 Punya Biswal The challenge response mechanism, or, how I can guess your coins by flipping my own
11/3/06 Arnab Bhattacharyya The direct product lemma, hardness amplification, and all that
11/17/06 Ning Xie Almost k-wise independence versus k-wise independence
12/1/06 Arnab Bhattacharyya The direct product lemma, hardness amplification, and all that, part II
12/8/06 Victor Chen Linearity Testing, Gowers Uniformity, and PCPs

Some Suggested/Requested Topics:



Approximation Algorithms Optimization/Convex Geometry Linear Algebra Large Data/Learning Data Structures Misc.

For questions or comments, contact Brendan Juba (first initial last name at alum dot mit).