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.

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

**[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 10: Lecture 11] Non-uniform complexity**

Kannan's circuit lower bound. Logarithmic-depth circuits.

Notes for lecture 11**Reading:**Section 6.7.

**[Oct 12: Lecture 12] Randomized computation**

RP, BPP, ZPP. Error reduction. Probabilistic algorithms.

Notes for lecture 12**Reading:**Sections 7.1-7.4.

**[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 9: Lecture 20] Zero-knowledge proofs**

Honest-verifier and dishonest-verifier perfect zero-knowledge proofs. Computational zero-knowledge proofs; perfect zero-knowledge arguments.

Notes for lecture 20**Reading:**Section 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).