**Lectures**Tuesdays and Fridays 1.30-3 in FIT 1-222**Instructor**Andrej Bogdanov, FIT 4-608-7, andrejb (a) tsinghua.edu.cn**Office hour**Tuesday 3-4 or by appointment

**Jan 27**Final grades for the class have been issued.**Dec 28**Take a look at the final project presentation schedule for next week. All the presentations are now scheduled for Thu Jan 4. We might run a bit overtime.

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

- Is every problem whose solutions are easy to verify also easy to solve?
- If not, can we still solve the problem most of the time, or solve it approximately?
- If yes, is it also easy to count how many solutions there are?
- How much can you learn by asking random questions?
- Can randomness be used to speed up computations, or the checking of proofs?

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 | |
---|---|---|---|

1 | Oct 9 | Introduction, P and NP | [pdf] |

2 | Oct 12 | NP completeness, hierarchy theorems | [pdf] |

3 | Oct 16 | The polynomial hierarchy, oracles | [pdf] |

4 | Oct 19 | Circuits, Karp-Lipton-Sipser theorem | [pdf] |

5 | Oct 23 | Circuits and machines with advice | [pdf] |

6 | Oct 26 | Randomized algorithms | [pdf] |

7 | Oct 30 | Lower bounds for constant depth circuits | [pdf] |

8 | Nov 2 | Approximating parity, hardness vs. randomness | [pdf] |

9 | Nov 6 | The Nisan-Wigderson generator | [pdf] |

10 | Nov 9 | Interactive proofs | [pdf] |

11 | Nov 13 | Counting problems and interactive proof for #SAT | [pdf] |

12 | Nov 16 | Probabilistically checkable proofs | [pdf] |

13 | Nov 20 | Probabilistically checkable proofs for NEXP | [pdf] |

14 | Nov 23 | The multilinearity test | [pdf] |

15 | Nov 27 | Circuit lower bounds from derandomization | [pdf] |

16 | Nov 30 | Random self reducibility | [pdf] |

17 | Dec 4 | Hardness amplification | [pdf] |

18 | Dec 7 | Average-case complexity | [pdf] |

19 | Dec 11 | One-way functions and pseudorandom generators | [pdf] |

20 | Dec 14 | The Goldreich-Levin theorem | [pdf] |

21 | Dec 18 | Pseudorandom functions | [pdf] |

22 | Dec 21 | Natural proofs | [pdf] |

Dec 25 | Christmas day, class cancelled | ||

23 | Dec 28 | Zero-knowledge proofs | |

Jan 1 | New year's day |
||

Jan 4 | Project presentations |

- Homework 4 due Tue Dec 18 and solutions
- Homework 3 due Fri Nov 30 and solutions
- Homework 2 due Fri Nov 16 and solutions
- Homework 1 due Tue Oct 30 and solutions

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

**Basic complexity classes**P and NP, decision versus search, diagonalization and its limitations, the polynomial-time hierarchy, non-uniform models.**Randomness and counting**BPP, ZPP and RP, counting solutions, Valiant-Vazirani, approximate counting, Toda's theorem.**Small space computations**L and NL, Savitch theorem, NL = coNL, graph connectivity and randomized logspace.**Interactive proofs**AM and IP, round reduction, AM versus NP, IP versus PSPACE.

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.

**Pseudorandomness**The Nisan-Wigderson generator, expanders and Reingold's theorem, epsilon-biased sets, Goldreich-Levin theorem and cryptographic generators.**Average-case complexity**Distributional problems, heuristic algorithms, average-case completeness, one-way functions, random self-reductions, hardness amplification.**Circuit lower bounds**Bounds for small depth circuits, connection to pseudorandomness, natural proof limitations.**Inapproximability**The PCP theorem, combinatorial view of proof systems, gap amplification, Håstad's verifier for 3SAT, unique games.

**Prerequisites**Familiarity with discrete mathematics, algorithms, proofs, computability, NP completeness.**Scribe notes**We will keep "scribe notes" of each lecture and this will serve as a primary reference for the material covered in the course. Each set of scribe notes will be prepared by two students with my assistance and should be available at most a week after the lecture. Please use lecheader.tex as a preamble for your notes. You can see the source for lecture 1 notes as an example.**References**Other sources that will be helpful are Luca Trevisan's lecture notes on complexity and the draft of the book Complexity theory: A modern approach by Sanjeev Arora and Boaz Barak. A good reference for some of the material is the draft of another new book by Oded Goldreich.**Grading and homeworks**Your grade will be determined from class attendance, scribe notes, homeworks, and a final project. Homeworks will be issued periodically (5 or 6 during the semester). You are encouraged to collaborate on them as long as you write up your own solutions.**Final project**For your final project you will be expected to do a bit of independent reading, a presentation in class, and a short report.