CSL853: Topics and reference material

  • Jan 7: Theory of Computation Recap.

  • Jan 9: Theory of Computation Recap.

  • Jan 16: P, NP, Cook-Levin Theorem.

  • Jan 21: Cook-Levin Theorem, Decision vs Search, co-NP.
    • Scan for Cook-Levin Theorem (PDF)

  • Jan 23: Diagonalization (Time Hierarchy Theorems, Ladner's Theorem).

  • Jan 28: Diagonalization (Ladner's Theorem, Relativization).

  • Jan 30: Space Complexity (PSPACE, L, NL, TQBF, Savitch's Theorem).

  • Feb 4: Space Complexity (Logspace reduction, NL-complete, NL=coNL).
    • Minor-1

  • Feb 11: The Polynomial Hierarchy.

  • Feb 13: Boolean Circuits (P/poly, Karp-Lipton Theorem, circuit lower bounds etc.).

  • Feb 20: Boolean Circuits (NC and AC).
    • Additional material: Lecture notes from Emanuele Viola (PDF1) (PDF2).

  • Feb 25: Randomized Computation (BPP, PRIMES, PIT).

  • Mar 11: Randomized Computation (RP, coRP, ZPP, Adleman's Theorem, Sipser-Gacs-Lautemann Theorem).

  • Mar 13: Complexity of Counting (#P, PP, #P-complete, Valiant's Theorem).

  • Mar 18: Complexity of Counting (Valiant's Theorem, Valiant-Vazirani Theorem, Toda's Theorem).

  • Mar 20: Complexity of Counting (Toda's Theorem).
    • Minor-2

  • Mar 27, Apr 01, 02: Interactive proofs (IP, GNI, QNR in IP, P^#P in IP, IP=PSPACE, AM, MA, Set lower bound protocol)

  • Apr 15: PCP and Hardness of Approximation (Introduction)

  • Apr 17: PCP and Hardness of Approximation (NP=PCP(log(n), 1) <=> Inapproximability)

  • Apr 18: PCP and Hardness of Approximation (NP \subseteq PCP(poly(n), 1), MAX-3SAT)

  • Apr 22: PCP and Hardness of Approximation (BLR Linearity Test, Label Cover, 2P1R proofs)

  • Apr 24: PCP and Hardness of Approximation (Soundness amplification of 2P1R games)

  • Apr 29: PCP and Hardness of Approximation (Set Cover)

  • May 01: PCP and Hardness of Approximation (UGC and Max-Cut)