This course will be an introductory graduate-level course in computational complexity theory.
It is introductory in the sense that no prior knowledge in complexity theory is assumed, except that it is
assumed students are familiar and comfortable with the notions of Turing machines, languages, classes, P/NP, and NP-completeness
(but even these concepts will be reviewed quickly in the first lecture).
On the other hand, the course will cover some fairly advanced (and abstract) material at a relatively quick pace; therefore,
it is assumed that (1) students have "mathematical maturity" (e.g., are comfortable with proofs and abstract reasoning);
(2) students are interested in the material; and
(3) students are willing to spend time outside of class in order to better understand the material presented in class.
We will follow the text by Arora and Barak, supplemented with lecture notes giving further details or covering topics not in that text.
The course will be similar to the previous offering.
If you are unsure whether this class is appropriate for you, I recommend you look at the Arora-Barak textbook (as well as the previous offering of the course) to see whether you (a) find the topics interesting, and (b) find the level of difficulty appropriate.
General Information and Announcements
Professor:Jonathan Katz (jkatz AT cs.umd.edu).
Office: 3225 A.V. Williams Building. Office hours: by appointment.
Teaching Assistant: Daniel Apon (dapon AT umd.edu).
Office hours: Mondays after class until 4:30, Tuesdays 12-2 in 3204 AV Williams.
The class meets Mondays and Wednesdays from 2 - 3:15 in 3258 AV Williams
The final course grade will be based on homework (20%), a midterm (40%), and a final (40%).
Class participation and attendance will be taken into account for borderline cases.
Late homeworks will be not be accepted without prior approval from the instructor.
You may work on the homeworks in groups subject to the following rules: (1) each student must write their own solutions to hand in, and (2) each student must write the name of the other students they worked with.
The final exam is available. It is due at 3:30 on Monday, Dec. 19.
The entire set of lecture notes is available, in one file, here.
Readings refer to Arora-Barak. Feedback and corrections on the lecture notes are always appreciated!
[Aug 31: Lecture 1] Introduction; P and NP Review of Turing machines, universal Turing machines, and uncomputable functions.
Notes for lecture 1 Reading: Chapter 0; Sections 1.1-1.5. (Section 1.7 was mentioned in class, but is optional.)
[Sept 7: Lecture 2] P, NP, coNP, and NP-Completeness P vs. NP; NP vs. coNP; and NP-completeness.
Notes for lecture 2 Reading: Sections 1.6, 2.1, 2.2, 2.6, and 2.7.
[Sept 12: Lecture 3] More on NP and NP-Completeness NP-completeness of SAT and other problems.
Search vs. decision and self-reducibility.
Notes for lecture 3 Reading: Sections 2.3, 2.4, and 2.5.
[Sept 14: Lecture 4] Diagonalization Time/space hierarchy theorems.
Notes for lecture 4 Reading: Sections 3.1, 3.2, and 4.1.3.
[Sept 19: Lecture 5] Diagonalization Ladner's theorem. Relativization of the P vs. NP question.
Notes for lecture 5 Reading: Sections 3.3 and 3.4.
[Sept 21: Lecture 6] Space complexity PSPACE and PSPACE-completeness; NL and NL-completeness.
Notes for lecture 6 Reading: Section 4.1 and parts of Sections 4.2 and 4.3.
[Sept 26: Lecture 7] Space complexity
Savitch's theorem; the Immerman-Szelepcsenyi theorem.
Notes for lecture 7 Reading: Sections 4.2 and 4.3.
[Sept 28: Lecture 8] The polynomial hierarchy The polynomial hierarchy. Time-space tradeoffs for SAT.
Notes for lecture 8 Reading: Sections 5.1-5.4.
[Oct 3: Lecture 9] The polynomial hierarchy, non-uniform complexity PH in terms of oracle machines. Introduction to non-uniform complexity.
Notes for lecture 9 Reading: Sections 5.5, 6.1, and 6.2.
[Oct 5: Lecture 10] Non-uniform complexity Circuit complexity and P/poly. The Karp-Lipton theorem. Logarithmic-depth
circuits.
Notes for lecture 10 Reading: Sections 6.3, 6.4, 6.5, 6.7.
[Oct 17: Lecture 13] Randomized computation Relation of BPP to the polynomial hierarchy and non-uniform computation.
BPP-completeness and promise problems.
Notes for lecture 13 Reading: Section 7.5.
[Oct 19: Lecture 14] Randomized space complexity
RL and BPL. Random walks on undirected graphs.
Notes for lecture 14 Reading: Sections 7.7 and 21.1.
[Oct 24: Lecture 15] Randomized space complexity
Markov chains, and random walks on undirected graphs, part 2.
Notes for lecture 15 Reading: None.
[Oct 26: Lecture 16] Interactive proofs Interactive proofs, MA, and AM.
Notes for lecture 16 Reading: Sections 8.1, 8.2.
[Oct 31: Lecture 17] Interactive proofs Graph non-isomorphism in AM.
Notes for lecture 17 Reading: Section 8.2.
[Nov 2: Lecture 18] Interactive proofs An interactive proof for coNP.
Notes for lecture 18 Reading: Section 8.3
[Nov 7: Lecture 19] Interactive proofs
IP=PSPACE.
Introduction to zero-knowledge proofs.
Notes for lecture 19 Reading: Sections 8.3, 9.4.
[Nov 14: Lecture 21] The PCP theorem
The PCP theorem and applications to proving inapproximability.
Notes for lecture 21 Reading: Sections 11.1-11.4.
[Nov 16: Lecture 22] The PCP theorem
A proof that NP is in PCP(poly, 1), part 1.
Notes for lecture 22 Reading: Section 11.5.
[Nov 21: Lecture 23] The PCP theorem; the complexity of counting
A proof that NP is in PCP(poly, 1), part 2.
#P and #P-completeness.
Notes for lecture 23. (The part about PCP is
contained in the notes for the previous lecture.)
Reading: Sections 17.1-17.3.
[Nov 28: Lecture 24] The complexity of counting
Hardness of unique-SAT. Approximating #P with an NP oracle. Toda's theorem.
Notes for lecture 24 Reading: Section 17.4.
[Nov 30: Lecture 25] Time-bounded derandomization Finish Toda's theorem. Complexity-theoretic pseudorandom generators. The Nisan-Wigderson construction.
Notes for lecture 25 Reading: Sections 20.1 and 20.2.
[Dec 5: Lecture 26] MIP = NEXP (guest lecture by Daniel Apon)
MIP, MIP=NEXP.
Notes for lecture 26
[Dec 7: Lecture 27] Space-bounded derandomization, error reduction Unconditional derandomization for space-bounded algorithms using Nisan's PRG. Error
reduction using Nisan's PRG.
Notes for lecture 27 Reading: Section 21.6.
[Dec 12: Lecture 28] Circuit lower bounds
Parity is not in AC0. Natural proofs.
Notes for lecture 28 Reading: Sections 14.1, 23.1-23.3 (note that the proof in Section 14.1 is different from the one given in class).