Computational Complexity

ITCS, Tsinghua University, Fall 2007

Recent Announcements

Course Description

Computational complexity studies the inherent power and limitations of various computational processes and phenomena, be they natural, engineered, or imaginary. Here are some examples:

Complexity theory does not yet know the definitive answers to these questions, but it shows that they (and many others) are deeply interconnected. In this course we will study the methodology and some of the tools that are used to establish these connections.

The course will cover ''classical'' topics in complexity theory as well as some recent developments.


date topic notes
1Oct 9 Introduction, P and NP [pdf]
2Oct 12 NP completeness, hierarchy theorems [pdf]
3Oct 16 The polynomial hierarchy, oracles [pdf]
4Oct 19 Circuits, Karp-Lipton-Sipser theorem [pdf]
5Oct 23 Circuits and machines with advice [pdf]
6Oct 26 Randomized algorithms [pdf]
7Oct 30 Lower bounds for constant depth circuits [pdf]
8Nov 2 Approximating parity, hardness vs. randomness [pdf]
9Nov 6 The Nisan-Wigderson generator [pdf]
10Nov 9 Interactive proofs [pdf]
11Nov 13 Counting problems and interactive proof for #SAT [pdf]
12Nov 16 Probabilistically checkable proofs [pdf]
13Nov 20 Probabilistically checkable proofs for NEXP [pdf]
14Nov 23 The multilinearity test [pdf]
15Nov 27 Circuit lower bounds from derandomization [pdf]
16Nov 30 Random self reducibility [pdf]
17Dec 4 Hardness amplification [pdf]
18Dec 7 Average-case complexity [pdf]
19Dec 11 One-way functions and pseudorandom generators [pdf]
20Dec 14 The Goldreich-Levin theorem [pdf]
21Dec 18 Pseudorandom functions [pdf]
22Dec 21 Natural proofs [pdf]
Dec 25 Christmas day, class cancelled
23Dec 28 Zero-knowledge proofs
Jan 1 New year's day
Jan 4 Project presentations


Tentative Course Topics

In the first part of the course we will focus on the following topics.

Here are some topics that we may talk about in the second part. This list should provide a representative sample though I do not expect we will have enough time to touch upon all of them.

Course Information