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) ~~3/31~~	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:

Feigenbaum and Fortnow. Random Self-reducibility of Complete Sets. SICOMP 1993.
Bogdanov and Trevisan. On Worst-case to Average-case Reductions for NP Problems. FOCS 2003. (link)
Akavia, Goldreich, Goldwasser, and Moshkovitz. On Basing One-way Functions on NP-hardness. STOC 2006. (link)
Pass. On Arthur-Merlin Games and the Possibility of Basing Cryptography on NP-hardness. CCC 2006. (link)

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: http://yury.name/talks.html)
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:

Crypto/Complexity

Paul W. Goldberg, Christos H. Papadimitriou: Reducibility among equilibrium problems. STOC 2006: 61-70
Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou: The complexity of computing a Nash equilibrium. STOC 2006: 71-78
Xi Chen and Xiaotie Deng: Settling the Complexity of 2-Player Nash-Equilibrium. FOCS 2006
Anup Rao: Extractors for a constant number of polynomially small min-entropy independent sources. STOC 2006: 497-506
Oded Goldreich, Shafi Goldwasser, Dana Ron: Property Testing and its Connection to Learning and Approximation. J. ACM 45(4): 653-750 (1998)
Y. Lindell and B. Pinkas: A Proof of Security of Yao's Protocol for Two-Party Computation.
Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby: A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28(4): 1364-1396 (1999)
Salil P. Vadhan: An Unconditional Study of Computational Zero Knowledge. FOCS 2004: 176-185
Amit Sahai, Salil P. Vadhan: A Complete Promise Problem for Statistical Zero-Knowledge. FOCS 1997: 448-457
Any of the papers on lattice-based cryptography
Irit Dinur: The PCP theorem by gap amplification. STOC 2006: 241-250
Intro to Average-Case Complexity (see Andrej Bogdanov and Luca Trevisan: Average-Case Complexity)
Neeraj Kayal, Nitin Saxena: Polynomial Identity Testing for Depth 3 Circuits. IEEE Conference on Computational Complexity 2006: 9-17
Russell Impagliazzo: Hard-Core Distributions for Somewhat Hard Problems. FOCS 1995: 538-545
Leslie Valiant: Holographic Algorithms. ECCC Report TR05-099
Leslie Valiant: Quantum circuits that can be simulated classically in polynomial time. SIAM J. Computing, 31(4): 1229-1254, 2002.

Algorithms

Approximation Algorithms

Kamal Jain: A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica 21:39-60, 2001.
M.X. Goemans and D.P. Williamson: A General Approximation Technique for Constrained Forest Problems. SIAM J. Computing, 24:296-317, 1995.
Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani: An Optimal Algorithm for On-line Bipartite Matching. STOC 1990: 352-358.
Frank Thomson Leighton, Bruce M. Maggs, Satish Rao: Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps. Combinatorica 14:167-186, 1994.
Rina Panigrahy, Sundar Vishwanathan: An O(log* n) Approximation Algorithm for the Asymmetric p-Center Problem. J. Algorithms 27:259-268, 1998.
Narendra Karmarkar, Richard M. Karp: An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem. FOCS 1982: 312-320.
L. A. Wosley: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4):385-393, 1982.

Optimization/Convex Geometry

Luis Rademacher, Santosh Vempala: Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. FOCS 2006: 729-738.
John Dunagan, Santosh Vempala: A simple polynomial-time rescaling algorithm for solving linear programs. STOC 2004: 315-320.
Orlin. A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization. IPCO 2007. LNCS 4513.

Linear Algebra

Ravi Kannan, Santosh Vempala: Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. FOCS 1998: 370-378
Daniel A. Spielman, Shang-Hua Teng: Spectral Partitioning Works: Planar Graphs and Finite Element Meshes. FOCS 1996: 96-105.

Large Data/Learning

Ronald Fagin, Ravi Kumar, D. Sivakumar: Comparing Top k Lists. SIAM J. Discrete Math. 17:134-160, 2003.
Moses Charikar: Similarity estimation techniques from rounding algorithms. STOC 2002: 380-388.
P. Drineas, Ravi Kannan, Alan Frieze, Santosh Vempala and V. Vinay: Clustering in large graphs and matrices. SODA 1999.
Jon M. Kleinberg, Mark Sandler: Using mixture models for collaborative filtering. STOC 2004: 569-578.
C. H. Papadimitriou, P. Raghavan, H. Tamaki, S. Vempala. Latent semantic indexing: A probabilistic analysis. ACM Principles of Database Systems, 1998.
Martin Zinkevich: Online Convex Programming and Generalized Infinitesimal Gradient Ascent. ICML 2003: 928-936.

Data Structures

Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48:723-760, 2001.
Valerie King, Garry Sagert: A Fully Dynamic Algorithm for Maintaining the Transitive Closure. J. Comput. Syst. Sci. 65:150-167, 2002.

Misc.

Furer. Faster Integer Multiplication. STOC 2007.
Manindra Agrawal, Neeraj Kayal, Nitin Saxena: PRIMES is in P. Annals of Mathematics 160(2): 781-793, 2004.
Elias Koutsoupias, Christos H. Papadimitriou: On the k-Server Conjecture. J. ACM 42:971-983, 1995.
Interior Point Methods (See Renegar. "A Mathematical View of Interior-Point Methods in Convex Optimization". MPS-SIAM.)
Graph Minor Theorem (See Bienstock, Langston. "Algorithmic Implications of the Graph Minor Theorem" and Diestel. "Graph Theory", 3rd Edition.)

For questions or comments, contact Brendan Juba (

MIT Complexity Student Reading Group

Current topic:

Other nominated topics:

Past terms

Crypto/Complexity

Algorithms