CSE 201a, Advanced Complexity Theory, Spring, 2011

Prof. Russell Impagliazzo

Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 92093-0114

Office: 4111 Applied Physics and Mathematics Building (APM)
Phone: (858) 534-1332; Fax: (858) 534-7029;
Email: russell@cs.ucsd.edu

    Class handouts
  1. First lecture notes, March 29, Razborov-Smolensky
  2. Second lecture notes, March 31, Razborov-Smolensky continued
  3. Third lecture notes, Hard problems in the exponential time hierarchy , April 7
  4. lecture notes, April 12, Oblivious TMs
  5. lecture notes, April 14, Probabilistic polynomial time and derandomization, part 1
  6. A survey paper that sketches some issues in complexity theory
  7. Class Description