Luca Trevisan
CS 278 -- Computational Complexity
[Info]
[Topics]
This course will roughly be divided into two parts: we will start with "basic" and "classical" material
about time, space, P versus NP, polynomial hierarchy and so on, including moderately modern and advanced
material, such as the power of randomized algorithm, the complexity of counting problems, and the
average-case complexity of problems. In the second part, we will focus on more research oriented material,
to be chosen among: (i) PCP and hardness of approximation; (ii) lower bounds for proofs and circuits;
and (iii) derandomization and average-case complexity.
Jin-Yi Cai
CS810: Introduction to Complexity Theory (Models and Formalisms of Computation)
[Info]
[Topics]
We will start with a review of some topics from a typical undergraduate course in Theory of Computing,
including such concepts as Turing machines, recursive functions, computability and incomputability,
and the Church-Turing thesis.
We then consider time and space bounded computation; deterministic and non-deterministic time classes
and space classes, LOGSPACE, NL, P, NP, PSPACE, etc; Savitch's theorem, Immerman-Szelepcsenyi Theorem,
Cook-Levin Theorem, NP-completeness and P-completeness, Karp's problems. We will also introduce randomized
complexity classes ZPP, RP, BPP; polynomial time hierarchy; Sipser-Lautemann Theorem, interactive proofs,
Arthur-Merlin Games, LFKN protocol and Shamir's Theorem (with a proof by Shen, using "diagram chasing"),
probabilistically checkable proofs; non-uniform complexity, Karp-Lipton Theorem, graph non-isomorphism
problem; circuit lower bounds, bounded depth circuits; Counting problems and Valiant's theory, Permanent
and determinant problem. If time permit we may also discuss other topics such as pseudorandom generators
and hardness versus randomness, or dichotomy theorems.
Date: Fall 2008
Level: First year graduate
Lecturer:
Jin-Yi Cai
Comment: The course notes are clear.