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] |
|
|
