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

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 | 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) | 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)

- Multiparty communication complexity of disjointness
- Hardness of learning halfspaces

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 | (cancelled) | |

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 | | (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 |

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) |

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 |

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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 ().