Complexity Theory

Course Instructor: Anup Rao (anuprao@cs.washington.edu), office hours: Tuesdays 2:30-3:30 pm, in CSE 656.

TA: Cyrus Rashtchian (cyrash@cs.washington.edu), office hours: Wednesdays 5-6pm, in CSE 306.

Computational Complexity is the mathematical investigation of several broad questions that have to do with computation. What is computation? What is hard to compute and why? What is easy to compute? How useful is access to various resources like time, memory, randomness and advice?

In this class, we seek to give a rigorous mathematical framework that will enable us to answer some of these questions. We shall explore what is known about the most famous open problem in computer science (the P vs NP question).

Complexity theory has been around as an area for more than 50 years, but it is still in its infancy. It is notorious for generating the hardest open questions in computer science.

Course Resources:

The class website is on canvas, where you can access lecture notes, homework and a discussion board.

Grading will be based on biweekly homework, a take-home midterm and an in-class final. Collaboration on the homework is encouraged, but all answers should be written up individually.

Tentative Schedule:

Week 1 [3/29, 3/31]

1. Basic definitions.
1. Turing Machines
2. Boolean Circuits
3. Simulation of Turing Machines by Circuits.

Week 2 [4/5, 4/7]

1. Diagonalization.
1. Halting Problem
2. Godel’s Incompleteness Theorem
3. Hierarchy Theorem
1. Counting lower bounds
1. Hierarchy Theorems

Week 3 [4/12, 4/14]

1. P vs NP
1. Basic definitions
2. NP-hardness, NP-completeness
3. Circuit-SAT

Week 4 [4/19, 4/21]

1. NP-complete graph problems
2. The problem with using diagonalization on NP
1. Space
1. Savitch’s Algorithm
2. NL, RL, PSPACE
3. PSPACE completeness

Week 5 [4/26, 4/28]

1. Interactive Proofs for Permanent
2. IP = PSPACE

Midterm Exam.

Week 6 [5/3, 5/5]

1. Randomized Complexity
1. Pseudorandom generators
2. Nisan-Wigderson’s Generator

Week 7 [5/10, 5/12]

1. SL = L
1. Restricted Circuits
1. AC0, Switching Lemma
2. Approximations by polynomials

Week 8 [5/17, 5/19]

1. Monotone circuits, Lower bound for clique
1. Communication Complexity
1. Monotone depth hierarchy

Week 9 [5/24, 5/26]

1. Data structure lower bounds
2. Extension complexity lower bounds

Week 10 [5/31, 6/3]

1. PCP Theorem and Hardness of Approximation

Final Exam