CSE 201a, Advanced Complexity Theory, Fall, 2004

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

Russell's 201a Office Hours: TBA

Russell's 202 Office Hours: TBA

Web-site for Spring 2003 section of this class
    Class handouts
  1. Sanjeev Arora's textbook
  2. A survey paper that sketches some issues in complexity theory
  3. Class Description
  4. Midterm : Due November 18
  5. First Lecture Notes (2003)
  6. Lecture Notes (2003): Non-uniform classes and circuit complexity
  7. Lecture Notes (2003): the Polynomial Hierarchy and Approximate counting
  8. Lecture Notes (2003): Approximate counting continued
  9. Lecture Notes (2003): Learning
  10. Lecture Notes (2003): The Isolation Lemma