Computational complexity and interactive protocols

Syllabus

Nondeterministic time hierarchy and hierarchy for probabilistic computation

BPP and polynomial hierarchy

Time-space trade-off for SAT

Isolation Lemma and Toda's Theorem

Pseudo-random generators, Nisan's pseudo-random generator

Interactive protocols - Arthur-Merlin games (class AM, IP=PSPACE)

Multi-prover interactive protocols (MIP=NEXP)

Annotation

This course extends the basic course on computational complexity (NTIN063). It covers hierarchy theorems for probabilistic computation, time-space trade-offs for SAT, Toda's Theorem, pseudo-random generators and interactive protocols.