CSE 201a, Advanced Complexity Theory, Fall, 2004
Department of Computer Science and Engineering
University of California, San Diego
La Jolla, CA 920930114
Office: 4111 Applied Physics and Mathematics Building (APM)
Phone: (858) 5341332; Fax: (858) 5347029;
Email: russell@cs.ucsd.edu
Russell's 201a Office Hours: TBA
Russell's 202 Office Hours: TBA
Website for Spring 2003 section of this class
Class handouts

Sanjeev Arora's textbook

A survey paper that sketches some
issues in complexity theory

Class Description

Midterm : Due November 18

First Lecture Notes (2003)

Lecture Notes (2003): Nonuniform classes and circuit complexity

Lecture Notes (2003): the Polynomial Hierarchy and Approximate counting

Lecture Notes (2003): Approximate counting continued

Lecture Notes (2003): Learning

Lecture Notes (2003): The Isolation Lemma