CSE 201a, Advanced Complexity Theory, Spring, 2011
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
-
First lecture notes, March 29,
Razborov-Smolensky
-
Second lecture notes, March 31,
Razborov-Smolensky continued
-
Third lecture notes, Hard problems
in the exponential time hierarchy , April 7
-
lecture notes, April 12,
Oblivious TMs
-
lecture notes, April 14,
Probabilistic polynomial time and derandomization, part 1
-
A survey paper that sketches some
issues in complexity theory
-
Class Description