Name of the course: | Computational Complexity | |
---|---|---|
Instructor: | Jaikumar Radhakrishnan jaikumar@tifr.res.in |
|
Lecture timings: | Mondays, Wednesdays, Fridays (10:00am to 11:00am). We begin at 9:45am with a 15 minute review. | |
Text books: |
|
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). |