Posted by: jonkatz | December 12, 2011

Lecture notes on complexity theory

I taught Complexity Theory this past semester, and spent an inordinate amount of time — really, too much time — writing detailed lecture notes for each class. I figure I may as well advertise them in the hopes that others will find them useful. The full set of notes (almost 130 pages!) is available here.

Standard disclaimer: While the notes themselves are in excellent shape, I did not do much “final polishing” before posting them online. In particular, I am inconsistent with how I handle references and I apologize to anyone who feels their work has been slighted.

Comments (and corrections) on the notes are very welcome!



  1. It seems like a good course. I am interested in the “mix and match” approach to source material you used. Did you “assign” any particular text(s) for your class?

    How much time per lecture was it? How many hours total?

  2. Thank you sir, that’s very generous of you 🙂

  3. Paul, what do you mean by “mix and match approach”?

    The assigned text was Arora-Barak. Lectures were 75 minutes, and I gave 27 lectures (I missed two classes).

  4. Terrific! Thanks tons.

    I have read just a few pages. Perhaps 2.3.1 should instead read “… capturing the intuition that if L is harder than L’, then an algorithm for deciding L should be useful for deciding L’.”

  5. Ugh. I really should read the footnotes! You do say, “at least as hard to solve,” which is the better formulation, yes?

  6. Hi Jon,

    What I meant by “mix and match” was that your primary references seemed to be to a mix of sources, not just the Arora-Barak text. I am impressed by the selection and level, and what you were able to cover in that amount of time. I have taught from pre-publication versions of the A-B text’; from your notes I can see your discipline in allotting time to different parts of that material. I was also trying to gauge how much of this material would fit in our terms: (We have twenty 80 minute classes per quarter.)

  7. Tyler, thanks for the correction (there was indeed a typo). Feel free to email me any future corrections.

    Paul, it’s a bit funny to hear you say that — I was planning to cover slightly more material at the start of the semester! (Some topics took longer to cover than I had originally planned.) As far as references go, I only ever referred the students to the lecture notes and Arora-Barak; the additional references were mainly included for historical purposes or for students looking for further information.

    I’ll follow up with a post in a day or two about what I would change next time I teach this course…

  8. Jon, thanks for the pointer. When I taught complexity in spring 2011, I used what Paul described as a “mix and match” approach. I recommended but did not require the Arora-Barak text, and often pointed students to others’ lecture notes. I might add some of your notes to the pool I refer and point students to next time I teach grad complexity.

    I did not write notes for the course, but had lecture summaries in a blog.
    The last lecture summary lists many of the specific theorems covered (our coverages seem similar, though I did not cover zero knowledge proofs or MIP=NEXP, and did a bit more nonuniform lower bounds).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: