CSC 5170: Theory of computational complexity

The Chinese University of Hong Kong, Spring 2010


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

Course Information


Notes will be provided for every lecture. The following two books are good references for much of the material we will cover.