198:538 Complexity of Computation

Rutgers University, Computer Science Department, Spring 2007

Recent Announcements

Course Description

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

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.


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