198:538 Complexity of Computation

Rutgers University, Computer Science Department, Spring 2007

• Lectures Hill 120, Tuesdays and Thursdays 3.20-4.40
• Instructor Andrej Bogdanov, adib(a)dimacs.rutgers.edu, CoRE 413. Office hours Thu 1-2 or by appointment.
• Teaching Assistant Nikolaos Leonardos, nileonar(a)cs.rutgers.edu. Office hours Mon 4-6.

Recent Announcements

• Apr 24 See the project presentation schedule for Thu Apr 26.
• Apr 21 The project reports are due by Mon Apr 30 (preferably by e-mail, but if you want to turn in a hard copy slide it under my door).
• Apr 19 Please email me the title of your project presentation.
• Apr 19 Project presentations will be in class on Thu Apr 26. Each presentation should take about 20 minutes. We will probably run a bit overtime so please let me know if you need to leave early.

Course Description

Computational complexity studies the inherent power and limitations of various computational processes, 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 on most instances, or solve it approximately?
• If yes, is it also easy to count how many solutions there are?
• What things can you be convinced of in a short conversation?
• Can random coins be used to speed up computations, or the checking of proofs?

Complexity theory does not yet know the 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
1	Jan 16	Introduction, P and NP Notes: Arora-Barak Chapters 1 and 2, Trevisan Lecture 1
2	Jan 18	NP completeness, hierarchy theorems Notes: Arora-Barak Chapter 3, Trevisan Lecture 1
3	Jan 23	The polynomial hierarchy, oracles Notes: Arora-Barak Chapter 5, Trevisan Lecture 3
4	Jan 25	Circuits, Karp-Lipton-Sipser theorem Notes: Trevisan Lecture 4
5	Jan 30	Randomized algorithms, polynomial identity testing Notes: Trevisan Lectures 5, 6
6	Feb 1	More on BPP, unique solutions Notes: Trevisan Lectures 5, 7
7	Feb 6	Counting problems, approximate counting Notes: Trevisan Lecture 8
8	Feb 8	Toda's theorem Notes: Proof of Toda's theorem
9	Feb 13	Worst-case and average-case equivalence for #P Notes: Trevisan Lecture 9
10	Feb 15	Average-case complexity for NP Notes: Average-case complexity
11	Feb 20	Average-case completeness Notes: From last lecture
12	Feb 22	One-way functions and pseudorandom generators Notes: One-way functions and pseudorandom generators
13	Feb 27	The Goldreich-Levin theorem Notes: Arora-Barak Chapter 10, Section 3
14	Mar 1	Space complexity Notes: Trevisan Lecture 2
15	Mar 6	Interactive proofs Notes: Arora-Barak Chapter 8, Trevisan Lecture 13
16	Mar 8	Interactive proofs for PSPACE Notes: IP = PSPACE
17	Mar 20	PCPs and constraint satisfaction problems Notes: Arora-Barak §18.1, §18.2
18	Mar 22	Local testing and local decoding Notes: Arora-Barak §18.4
19	Mar 27	Expanders and eigenvalues Notes: Random walks and expanders
20	Mar 29	More on expanders; the PCP theorem Notes: From last lecture; Arora-Barak §18.5
21	Apr 3	Arity reduction, regularizing, expanderizing Notes: Arora-Barak §18.5, omitted proofs
22	Apr 5	Alphabet reduction, gap amplification Notes: Arora-Barak §18.5
23	Apr 10	Finish gap amplification; Circuit lower bounds Notes: Trevisan lecture 19
24	Apr 12	Lower bounds for constant depth circuits via polynomials Notes: Trevisan lecture 19
	Apr 17	Classes cancelled campuswide
25	Apr 19	Circuit lower bounds via the switching lemma Notes: Trevisan lecture 20
26	Apr 24	Relativizing proofs and natural proofs Notes: Arora-Barak §3.5, Chapter 22
27	Apr 26	Project presentations

Homeworks

• Homework 4 due Tue Apr 10 and solutions
• Homework 3 due Tue Mar 20 and solutions
• Homework 2 due Tue Feb 20 and solutions
• Homework 1 due Tue Feb 6 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 Randomized complexity classes, 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.

• Average-case complexity Distributional problems, heuristic algorithms, average-case completeness, one-way functions, random self-reductions, hardness amplification.
• Pseudorandomness The Nisan-Wigderson generator, expanders and Reingold's theorem, Goldreich-Levin theorem and cryptographic generators.
• 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, parallel repetition, Håstad's verifier for 3SAT.

Course Information

• Prerequisites 198:509 (Foundations of computer science) and 198:513 (Data structures and algorithms), or familiarity with discrete mathematics, algorithms, and proofs.
• Sources Our main sources for the course 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, homeworks, and possibly a final project (if class size allows it). Homeworks will be issued periodically, and 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 short presentation in class, and a short report.