Computational Complexity

16:198:538           Fall 2013


Instructor: Shubhangi Saraf


Timing:  Mon 12 pm – 3 pm

Location:  HILL 005

Office hours: Mon 3pm – 4 pm (Hill 426)


Description: This course will serve as a graduate course in complexity theory.


Computational complexity is the study of what computational tasks can be achieved efficiently, or with limited computational resources. Though computer scientists and mathematicians have intensively studied this topic in the last several decades, we still understand very little about computational efficiency.  Although there have been some remarkable results giving some answers and insights into some of the questions, most of major questions are still unanswered. Indeed it seems almost shocking that we still don't know the answers to them. In this course we will cover classical results as well as more recent results leading up to the state of the art in the field. Along the way we will encounter many surprising connections, beautiful mathematics, and a host of intriguing questions.


Recommended Text: "Computational Complexity: A Modern Approach" by Arora and Barak.

Also available online:


Another great book (also available online):

"Computational Complexity: A conceptual Perspective" by Oded Goldreich


Prerequisites: It will be helpful to have some background in algorithms/discrete math, but no formal prerequisite will be enforced. If you do not satisfy the official prerequisites but are still interested in registering for the course, and you are concerned if you will be sufficiently prepared for the course, send an email to

The only real prerequisite is some mathematical maturity.


Homework/grading: There will be 3 problem sets. Students will also be required to scribe one (or possibly more) lecture.

Latex template for scribe notes:  Here is the sample file, and the preamble file that goes along with it


Homework 1 (due October 7)

Homework 2 (due November 4)

Homework 3 (due December 2)






§  Lecture 1 (09/09): Administrative details, course overview, Turing machines, complexity classes.    NOTES


§  Lecture 2 (16/09): NP-completeness, Cook-Levin Theorem, Hierarchy theorems.    NOTES


§  Lecture 3 (23/09):  Hierarchy Theorems, Ladner’s theorem, Oracles and relativization, space complexity NOTES


§  Lecture 4 (30/09):  PSPACE completeness, Savitch’s theorem, L, NL NOTES


§  Lecture 5 (07/10):  NL = co-NL, Alternations, Polynomial hierarchy NOTES


§  Lecture 6 (14/10):  TIME-SPACE tradeoffs, Boolean circuit complexity.  NOTES


§  Lecture 7 (21/10):  Karp-Lipton Thm, Randomized complexity, BPP in P/poly. NOTES 


§  Lecture 8 (28/10):  BPP in PH (Sipser Lautemann), Interactive proofs.  NOTES


§  Lecture 9 (04/11):  AM proofs, Goldwasser-Sipser, Co-NP in IP.  NOTES


§  Lecture 10 (11/11):  #SAT in IP, IP in PSPACE, PCP theorem.   NOTES


§  Lecture 11 (18/11):  PCP theorem and hardness of approximation, Local testing, local decoding  NOTES


§  Lecture 12 (25/11):  Linearity Testing (BLR), exponential length PCP for SAT  NOTES


§  Lecture 13 (02/12):  Proof of PCP theorem (by Dinur)


§  Lecture 14 (09/12):  Cancelled.   Make up class on Cryptography held on (19/11)















Tentative (and partial) list of topics:

·      Hierarchy theorems, Diagonalization, Relativization,

·      Alternations, NP completeness,

·      Space bounded computation, sublinear space algorithms

·      Randomness in computation, BPP, RP

·      Interactive proofs

·      Circuit lower bounds

·      Hardness versus randomness – derandomization, pseudorandom generators

·      PCP theorem, hardness of approximation