The class will roughly be organized as follows: The first 2/3 of the course will cover "standard" material on complexity theory (e.g., the material in lectures 1-12 of Goldreich's lecture notes); the remainder of the course will focus on more advanced topics (such as derandomization of space- and time-bounded algorithms, the PCP theorem, circuit lower bounds, learning theory, cryptography, and/or other topics).

If you are unsure whether this class is appropriate for you, I recommend you check out Goldreich's notes (referenced above) to make sure that you (a) find the topics interesting, and (b) find the level of difficulty appropriate. You can also feel free to email me with any questions.

The requirements are:

- Regular attendance
- Occasional
*graded*homeworks, with solutions expected to be typed using latex - There will be a midterm and a final
*only for those students taking the course for grad credit*

- The class meets Thursdays from 4:00 - 6:45 in 2118 CSIC.
**Homework guidelines:**Please use latex to write up your solutions. (It is ok for HW1 if you do not know latex. But the TA will hold a tutorial on using latex and you should use latex for subsequent homeworks.) You are welcome to use other sources, and speak with other students, in coming up with your solutions. However, you*must*write the solutions in your own words, and understand them, and you*must*reference any sources you used. (Failure to comply will be considered cheating.)**Professor:**Jonathan Katz (`jkatz AT cs`). Office: 3225 A.V. Williams Building. Office hours:**Note:**for the next few weeks, my schedule will vary week-to-week. Please email me if you would like to set up an appointment.**TA:**Ji-Sun Shin (`sunny AT cs`). Office hours: Thursday, 11:30 - 12:30 (in the TA room)- The books
*Computational Complexity*, by Papadimitriou, and*Introduction to the Theory of Computation*, by Sipser, are now available on reserve from the CS library. - The
**final exam**will be held in class on Dec. 8.

**[Sept 1: Lecture 1] Introduction to P and NP**

Introduction. Review of Turing machines, P, and NP. Time/space hierarchy theorems. NP completeness and reductions.

Notes for lecture 1

**[Sept 8: Lecture 2] NP completeness**

More on NP-completeness. Self-reducibility. Ladner's theorem.

Notes for lecture 2

**[Sept 15: Lecture 3] Deterministic and non-deterministic space complexity**

On co-non-deterministic languages. NL and NL-completeness. Savitch's theorem; the Immerman-Szelepcsenyi theorem.

Notes for lecture 3

**[Sept 22: Lecture 4] Non-uniform (circuit) complexity**

Introduction to circuit complexity and P/poly.

Notes for lecture 4

**[Sept 29: Distinguished lecture series]**

Class will be cancelled.

Everyone is encouraged to attend the**distinguished lecture**by Cynthia Dwork, being held in CSIC 1115 from 4-5.

**[Oct 6: Lecture 5] More on circuit complexity. Randomized computation**

The Lupanov bound on circuit size. Randomized complexity classes: RP, coRP, BPP. Error reduction using independent and pairwise-independent sample spaces.

Notes for lecture 5

**[Oct 13: Lecture 6] The polynomial hierarchy**

Mahaney's theorem. The polynomial hierarchy. The Karp-Lipton theorem.

Notes for lecture 6

**[Oct 20: Lecture 7] More on randomized computation**

ZPP and PP. The relation of BPP to P/poly and the polynomial hierarchy. Randomized space classes; random walks on undirected graphs.

Notes for lecture 7

**[Oct 27: Lecture 8] Random walks. Counting classes**

Markov chains and random walks on undirected graphs. #P and #P-completeness.

Notes for lecture 8

**[Nov 3: Lecture 9 (first half)] Midterm exam**

**[Nov 3: Lecture 9 (second half)] The complexity of counting**

Approximate counting.

Notes for lecture 9

**[Nov 10: Lecture 10] Unique solutions. Interactive proofs**

The Valiant-Vazirani theorem and hardness of finding unique solutions (see notes for lecture 9).

Interactive proofs. AM, MA, and their relation to IP. Round reduction for interactive proofs.

Notes for lecture 10

**[Nov 17: Lecture 11] IP = PSPACE**

More on AM, MA, and evidence that graph isomorphism is not NP-complete (see notes for lecture 10).

Arithmetization, coNP contained in IP and IP = PSPACE.

Notes for lecture 11

You may also find interesting a fascinating survey of the history of the IP = PSPACE result (and more)

**[Dec 1: Lecture 12] The PCP theorem and applications to hardness of approximation**

Introduction to PCP; applications to hardness of approximation. NP contained in PCP(poly, O(1)).

Notes on PCP and inapproximability and NP contained in PCP(poly, O(1))

**[Dec 8: Lecture 13] Final exam**

**Other notes**(things that we did not have time to cover this semester):