Tentative syllabus

Here is a very rough guideline for the list of topics we might cover in the course. This is almost certainly an ambitious plan and is subject to change based on time constraints. We will probably only be able to discuss a subset of these topics, and may not cover the topics necessarily in the order listed.

-------------------

Introducton: the big questions, Turing machines, Basic time and space
classes (P,NP,L,PSPACE,NL), Universal Turing machines, Hierarchy
theorems, Nondeterminism, NP-completeness and Cook-Levin theorem,
P-completeness;

Randomized complexity classes, Polynomial identity testing, Polynomial
time hierarchy, Non-uniform (circuit) classes, Karp-Lipton theorem.

Complexity of Unique-SAT, Approximate counting in the
hierarchy, Exact learning of circuits with oracles.

Space complexity: PSPACE and NL-completeness, Savitch's theorem, NL =
coNL, Relationship to parallel computation and NC circuit classes.

Counting classes, #P-completeness, The power of counting (Toda's
theorem).

The power of interaction: Graph nonisomorphism protocoal, Interactive
proofs for #SAT, IP=PSPACE, coNP unlikely to have short interactive
proofs.

Lower bounds and concrete complexity:
Parity doesn't have small depth circuits.
Some frontiers in circuit complexity:
- ACC_0 and multiparty communication complexity
- Log depth and rigidity
Time space trade-offs: Lower bounds for SAT;
Non-uniform model: Branching programs. Barrington's theorem.

Derandomization:
- Nisan's generator for low space machines
- Nisan-Wigderson: hardness vs randomness
- Hardness amplification and average-case hardness

Some vignettes:
- Cryptography in constant parallel time
- Natural proofs: a barrier to proving stronger circuit lower bounds
- Derandomization needs circuit lower bounds
- Quantum computing