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. ImmermanSzelepcsenyi theorem. Symmetric Logspace. USTConn. NisanTaShma theorem. 
Week 3 23, 25, 27 Feb 04 
Randomized spacebounded 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 SaksShiyu theorem: RL is subset of DSpace((log n)^1.5). 
Week 5 8, 10 Mar 04 
Polynomialsize circuits. Oracles. Reductions. Completeness. Polynomialtime hierarchy. 
Week 6 15, 17, 19 Mar 04 
Cook's theorem. Alternation. KarpLipton theorem: if NP has
polynomialsize circuits, then the hierarchy collapses. Randomized computation. Amplification. SipserGacsLauteman theorem: BPP in Sigma_2^P. 
Week 7 22, 24, 26 Mar 04 
Counting classes: PP, sharpP. Toda's theorem. MulumuleyVaziraniVazirani isolation lemma. BPP has poly size circuits. Interactive Proof Systems. The private coins protocol for Graph NonIso. The class AM[k]. If GISO is NPcomplete then the hierarchy collapses. 
Week 8 29, 31 Mar, 2 Apr 04 
Private Coins versus Public Coins. SharpP 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 3SAT. 
Week 10 12, 14 Apr 04 
The clause check polynomial. Lowdegree extensions.
The sumcheck 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). 