Theory of Computational Complexity PDF SLIDES

Theory of Computational Complexity

Instructor : Andrej Bogdanov
Textbook : Computational complexity A conceptual perspective. Oded Goldreich
Download slides from here

topic	reading
Computational problems. P and NP. Hierarchy theorems.	[pdf]
Circuits.	[pdf]
Constant depth circuits. Lower bounds.	[pdf]
Logarithmic space. Barrington and Immerman-Szelepcsényi theorems.	[pdf]
Randomized computation.	[pdf]
Pseudorandomness. The Nisan-Wigderson generator.	[pdf]
Random walks and eigenvalues.	[pdf]
Expanders. Undirected connectivity in log-space.	[pdf]
The polynomial-time hierarchy. Oracles.	[pdf]
Counting problems. Toda's theorem.	[pdf]
Interactive proofs. Guest lecture by Shengyu Zhang	[pdf]
Probabilistically checkable proofs.	[pdf]
Proof of the PCP theorem.	[pdf]