The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 532: Computational Complexity Essentials, Spring 2004
  CSE Home  About Us    Search    Contact Info 

Email
  Archive 
  Sign-up Instructions
Exercises
  Assignment 1
  Assignment 2
Lectures
  All lectures
  Lecture 1
  Lecture 2
  Lecture 3
  Lecture 4
  Lecture 5
  Lecture 6
  Lecture 7
  Lecture 8
  Lecture 9
  Lecture 10
  Lecture 11
  Lecture 12
  Lecture 13
  Lecture 14
  Lecture 15
  Lecture 16
  Lecture 17
   
CSE 532: Computational Complexity Essentials

TTh 12:00-1:20    EE1 025

Instructor: Paul Beame

This spring, in 532 we will cover many of the most important results and ideas in computational complexity from the last three decades. The topics below below are the target material for the course. The only background needed will be CSE 531.

Topics:

NP and above

  • Simulation of randomness by alternation: BPP in Polynomial-time Hierarchy (PH) (Sipser-Gacs,Lautemann)

  • Circuit complexity and P versus NP: NP in P/poly => PH collapses. (Karp-Lipton)

  • Counting problems and the class #P (Valiant)

  • Counting is as hard as the polynomial-time hierarchy: PH is in P#P (Toda)

  • Time-space tradeoffs for SAT (Fortnow,Fortnow-van Melkebeek)

Interactive and Probabilistically Checkable Proofs

  • Random quantifiers can replace Universal ones: IP=PSPACE (Shamir-Shen)

  • Round reduction and public coins: constant round IP=AM (Babai-Moran,Goldwasser-Sipser)

  • Graph Non-isomorphism and AM: ISOMORPHISM NP-complete => PH collapses (Boppana-Hastad-Zachos)

  • Polynomially checkable proofs exist for all of NEXP: NEXP=PCP(poly,poly) (Babai-Fortnow-Lund-Nisan)

  • PCP's and approximating Clique (Feige-Goldwasser-Lovasz-Safra-Szegedy)

  • PCP Theorem: NP=PCP(log, 1) (Arora-Lund-Motwani-Sudan-Szegedy,Arora-Safra)

Circuits and Complexity:

  • Switching Lemma:

    • Parity is hard for small depth circuits: Parity not in AC0 (Hastad)

  • Method of Approximation

    • Counting is hard for small depth circuits: Mod p not in AC0[q] (Razborov,Smolensky)

    • Monotone circuits for clique require exponential size (Razborov)

  • Natural Proofs (Razborov-Rudich)

Proof Complexity:

  • Pigeonhole Principle is hard for resolution (Haken,Beame-Pitassi,Ben Sasson-Widgerson)
Portions of the CSE 532 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 532 Web: © 1993-2004, Department of Computer Science and Engineering, University of Washington.