date | topic | reading | |
---|---|---|---|
1 | Jan 11 |
Computational problems. P and NP. Hierarchy theorems. | [pdf] |
2 | Jan 18 |
Circuits. | [pdf] |
3 | Jan 25 |
Constant depth circuits. Lower bounds. | [pdf] |
4 | Feb 1 |
Logarithmic space. Barrington and Immerman-Szelepcsényi theorems. | [pdf] |
5 | Feb 8 |
Randomized computation. | [pdf] |
Feb 2 |
No class, lunar new year | ||
6 | Feb 22 |
Pseudorandomness. The Nisan-Wigderson generator. | [pdf] |
7 | Mar 1 |
Random walks and eigenvalues. | [pdf] |
8 | Mar 8 |
Expanders. Undirected connectivity in log-space. | [pdf] |
9 | Mar 15 |
The polynomial-time hierarchy. Oracles. | [pdf] |
10 | Mar 22 |
Counting problems. Toda's theorem. | [pdf] |
11 | Mar 29 |
Interactive proofs. Guest lecture by Shengyu Zhang |
[pdf] |
Apr 5 |
No class, Easter holiday | ||
12 | Apr 12 |
Probabilistically checkable proofs. | [pdf] |
13 | Apr 19 |
Proof of the PCP theorem. | [pdf] |
Apr 26 Apr 27 |
Project presentations |
Notes will be provided for every lecture. The following two books are good references for much of the material we will cover.