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; it is assumed that (1) students 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.
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).
Note: You do not need to print out all of Goldreich's lecture notes,
especially since we will only be following them loosely (in particular, there
will be many topics we skip, a few that we add, and we will definitely cover
things in a different order). However, you may find it helpful to consult his
notes for further clarification of things covered in class.
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
There may also be occasional ungraded homeworks that will be discussed in class if there is interest.
General Information and Announcements
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 lecture notes are intended to supplement lectures, and do not necessarily cover everything discussed in class. They may also contain some things that we did not have time to cover in class.
[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):
This material is based upon work supported by the National Science Foundation under Grant Nos. 0310499, 0310751, 0426683, and 0447075.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.