Spring 2004: a graduate course on computational complexity

Name of the course: Computational Complexity
Instructor: Jaikumar Radhakrishnan
Lecture timings: Mondays, Wednesdays, Fridays (10:00am to 11:00am). We begin at 9:45am with a 15 minute review.
Text books:
[HUM] John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Education.
[P] Christos Papadimitriou. Computational Complexity.
[Notes] Lecture Notes from previous versions of this course: [1994] [1998].


We will begin with the classical results in space and time complexity: hierarchy theorems, closure under complementation. Then, we will study results in the area of randomized space complexity. The second part of the course will be concerned with time complexity. We will introduce the important complexity classes such as P, NP and sharp P, and the Alternating Turing Machine model. The latter part of the course will be devoted to the study of interactive proofs. After characterising NP as the class of properties that have easily verifiable proofs, we will study the effect of introducing randomness and interaction in the verification process. This will lead us naturally to Arthur-Merlin games. We will present the PCP theorem in detail, and show that that certain functions that were earlier believed to be hard to compute exactly are equally hard even to estimate approximately.

If there is time available in the end, we will discuss some results in circuit complexity and communication complexity.

The courses on Mathematical Structures and Automata \& Computability are prerequisites for this course.

The course grade will be based on homeworks


Week 1
11, 13 Feb 04
Linear speedup theorem. Time and Space hierarchy theorems. Time and Space constructible functions. Borodin's gap theorem.
Week 2
16, 18, 20 Feb 04
DSTConn. Log space reducibility. Savitch's theorem. Immerman-Szelepcsenyi theorem. Symmetric Logspace. USTConn. Nisan-TaShma theorem.
Week 3
23, 25, 27 Feb 04
Randomized space-bounded computation: RLogSpace, BPLogSpace. USTConn in RLogSpace. Chernoff bounds. Multiple access to the random tape: ZP*Log. Nisan's theorem: BPLog is a subset of ZP*Log.
Week 4
1, 4 Mar 04
Nisan's theorem: RL is subset of SC. The Saks-Shiyu theorem: RL is subset of DSpace((log n)^1.5).
Week 5
8, 10 Mar 04
Polynomial-size circuits. Oracles. Reductions. Completeness. Polynomial-time hierarchy.
Week 6
15, 17, 19 Mar 04
Cook's theorem. Alternation. Karp-Lipton theorem: if NP has polynomial-size circuits, then the hierarchy collapses.

Randomized computation. Amplification. Sipser-Gacs-Lauteman theorem: BPP in Sigma_2^P.

Week 7
22, 24, 26 Mar 04
Counting classes: PP, sharp-P. Toda's theorem. Mulumuley-Vazirani-Vazirani isolation lemma. BPP has poly size circuits. Interactive Proof Systems. The private coins protocol for Graph NonIso. The class AM[k]. If GISO is NP-complete then the hierarchy collapses.
Week 8
29, 31 Mar, 2 Apr 04
Private Coins versus Public Coins.

Sharp-P is subset of AM[poly]. The interactive sumcheck protocol.

Week 9
5, 7 Apr 04
Shamir's theorem: PSpace= AM[poly] (Shen's proof).

Probabilistically checkable proofs. Arithmetization of 3-SAT.

Week 10
12, 14 Apr 04
The clause check polynomial. Low-degree extensions. The sum-check protocol. NP is subset of PCP(log n, polylog n).

Reducing the number of probes. Dealing with fragmented inputs. Recursion. NP is subset of PCP (log n, 1).