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
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
- If not, can we still solve the problem most of the time, or solve
- 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
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.
||Introduction, P and NP
||NP completeness, hierarchy theorems
||The polynomial hierarchy, oracles
||Circuits, Karp-Lipton-Sipser theorem
||Circuits and machines with advice
||Lower bounds for constant depth circuits
||Approximating parity, hardness vs. randomness
||The Nisan-Wigderson generator
||Counting problems and interactive proof for #SAT
||Probabilistically checkable proofs
||Probabilistically checkable proofs for NEXP
||The multilinearity test
||Circuit lower bounds from derandomization
||Random self reducibility
||One-way functions and pseudorandom generators
||The Goldreich-Levin theorem
||Christmas day, class cancelled|
||New year's day
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,
- Randomness and counting BPP, ZPP and RP,
counting solutions, Valiant-Vazirani, approximate counting, Toda's
- 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,
- 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
notes on complexity and the draft of the book
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
- 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.