Theory of Computational ComplexityInstructor : 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] |
No comments:
Post a Comment