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

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment

Note: Only a member of this blog may post a comment.