CSC 5170: Theory of computational complexity
The Chinese University of Hong Kong, Spring 2010
- Lectures Mon 4:30-7:15
- Instructor Andrej Bogdanov, andrejb (a) cse.cuhk.edu.hk, SHB 926
- Office hours Fri 10.30-12.30 (or by appointment)
Lectures
|
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 |
|
Course Information
- Prerequisites Familiarity with algorithms and proofs.
- Grading and homeworks Your grade will be determined from
homeworks (30%), a take-home midterm exam (30%), and a final project (40%).
Three homeworks will be issued throughout the semester.
You are encouraged to collaborate on the homeworks as long as you
write up your own solutions.
- Final project For your final project you will be expected
to do some independent reading, a presentation in class, and a short
report. A list of suggested projects and more details will be provided
around the middle of the semester.
References
Notes will be provided for every lecture. The following two books are good references
for much of the material we will cover.
- Oded Goldreich. Computational complexity: A conceptual perspective.
Cambridge University Press, 2008.
- Sanjeev Arora and Boaz Barak. Computational complexity: A modern approach.
Cambridge University Press, 2009.