From: Paul Beame (beame@cs.washington.edu)
Date: Tue Mar 09 2004 - 12:06:59 PST
COURSE ANNOUNCEMENT for Spring 2004
CSE 532: Computational Complexity Essentials
TTh 12:00-1:20
MEB 243
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-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 AC^0
(Hastad)
* Method of Approximation
* Counting is hard for small depth circuits: Mod p not in AC^0[q]
(Razborov-Smolensky)
* Monotone circuits for clique require exponential size
(Razborov)
* Natural Proofs
(Razborov-Rudich)
Proof Complexity
* Pigeonhole Principle is hard for resolution
(Haken)
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Tue Mar 09 2004 - 12:07:13 PST