• Seminar Description and Mechanics
• Text: Oded Goldreich's Lecture Notes
• Participants
• Tentative Schedule

• References, Background Reading and Surveys

Description
This seminar will focus on important classical and modern results in complexity theory. We will aim to cover all of the following topics: time and space complexity (Savitch's and Immerman-Szelepcsènyi's theorems), the polynomial hierarchy, probabilistic complexity classes (BPP, RP, ZPP), interactive proof systems (IP, AM, MA), hardness of approximations and the PCP Theorem, counting and #P-completeness, circuit complexity, pseudorandomness and derandomization. If time permits, we will also study other advanced topics such as relativization, natural proofs, and average-case complexity. The exact syllabus of the seminar will depend greatly on the participants' interests.

Instructor: Professor Sally Goldman
Credit: 1 unit, Pass/Fail
Time and Place: Tuesdays 10-noon, Cupples II 101
Prerequisites: CSE 541T and CSE 547T or equivalent.
Requirements: One or two 2-hour lectures. Auditors welcome.

Text: Online Lecture Notes

We will follow Oded Goldreich's lecture notes:

• Introduction to Complexity Theory, Lecture notes for a 2-semester introductory course.

Other lecture notes available online:

• COS 522 Computational Complexity (Sanjeev Arora, Princeton University).
• CS 278 Computational Complexity (Luca Trevisan, Berkeley).
• CS 15-855 Computational Complexity Theory (Steven Rudich, CMU).
• 6.841/18.405J Advanced Complexity Theory (Madhu Sudan, MIT).

• "Minimum-weight triangulation is NP-hard," Wolfgang Mulzer and Guenter Rote (January 2006).
• "The PCP theorem by gap amplification," Irit Dinur (April 2005).
• "Undirected ST-Connectivity in Log-Space," Omer Reingold (November 2004).
• other recent STOC, FOCS, Complexity papers

Participants

• Professor Sally Goldman
• Professor Jeremy Buhler
• Ben Birnbaum
• Sharath Cholleti
• Brian Haynes
• Rob LeGrand
• Li-Yang Tan
• Ian Wehrman
• Eddy Westbrook

Tentative Schedule

Date	Topic	Speaker	Notes and Landmark papers
1/24	Introduction: P, NP, DTIME and Space Complexity	Ben	Lectures 1-4 of Goldreich's notes The Complexity of Theorem-Proving Procedures Stephen Cook, 1971 Reducibility among combinatorial problems Richard Karp, 1972
1/31	Non-Deterministic Space	Sharath	Lectures 5-6 Nondeterministic space is closed under complementation Immerman, 1988 The method of forced enumeration for nondeterministic automata Szelepscényi, 1988 1995 Gödel Prize
2/7	Randomized Computations	Sally	Lecture 7
2/14	Non-Uniform Polynomial Time (P/poly)	Eddy	Lecture 8
2/21	The Polynomial Hierarchy	Eddy	Lecture 9 The Polynomial-Time Hierarchy Stockmeyer, 1977
2/28	Pesudorandomness	Brian	Lectures 13-14
3/7	Counting and #P-completeness	Li-Yang	Lecture 10 The Complexity of Computing the Permanent Valiant, 1979
3/14	Spring Break!	.	.
3/21	Interactive Proof Systems and Zero-Knowledge Proofs	Li-Yang	Lectures 11 and 17 The Knowledge Complexity of Interactive Proof-Systems Goldwasser, Micali, Rackoff, 1985. IP = PSPACE Shamir, 1990. 1993 Gödel Prize
3/28	Computational Learning Theory	Sally	Lecture 25 Language identification in the limit Gold, 1967 A Theory of the Learnable Valiant, 1984 2003 Gödel Prize citataion for Freund and Shapire's work on Adaboost.
4/4	Computational Learning Theory, continued	Sally	Lecture 25
4/11	Probabilistically Checkable Proofs	Ben	Lectures 12 and 18 Approximating Clique is Almost NP-complete Frege, Goldwasser, Lovász, Safra, Szegedy, 1991. Proof verification and hardness of approximation problems Arora, Lund, Motwani, Sudan, Szegedy, 1992 Probabilistic Checking of Proofs: A New Characterization of NP Arora, Safra, 1992 2001 Gödel Prize
4/18	Metric Embeddings	Brian	Chapter 15, Embedding Finite Metric Spaces into Euclidean Spaces Jiri Matousek, Lecture Notes on Discrete Geometry
4/25	Probabilistically Checkable Proofs, continued. The Unique Games Conjecture	Sharath	Lectures 12 and 18

References / Background Reading

• The Complexity Zoo. Definitions of complexity classes.
• The Electronic Colloquium on Computational Complexity


• Theory of Computation: A Scientific Perspective, by Oded Goldreich and Avi Wigderson.
• History and Status of the P versus NP Question, by Michael Sipser.
• The P versus NP Poll, compiled by Bill Gasarch.

• CSE 533 The PCP Theorem and Hardness of Approximation, V. Guruswami and R. O'Donnell's course at UW.
• CS369: Metric Embeddings and Algorithmic Applications, Tim Roughgarden's course at Stanford.
• 15-859(J): Algorithmic Applications of Metric Embeddings, Anupam Gupta and R. Ravi's course at CMU.
• Inapproximability of Combinatorial Optimization Problems, a survey by Luca Trevisan.
• Zero-Knowledge, a tutorial by Oded Goldreich.