Computational Complexity

ITCS, Tsinghua University, Fall 2007

• 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

Recent Announcements

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

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:

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

Lectures

	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

Homeworks

• 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

Tentative Course Topics

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.

Course Information

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