- Arora-Barak
- Additional reference: Goldreich

- Complexity Theory courses at Berkeley, MIT, Princeton, Tel Aviv.
- Course notes by Goldreich.
- The Complexity Zoo.

- CS 579/ECE 579/MATH 578: Spring 2010
- Prof. Manoj M. Prabhakaran
- 12:30 PM to 1:45 PM Wednesday/Friday
- 1105 Siebel Center
- Credit: 4 hours
- CRN: 41446

This course is an introduction to the theory of computational complexity.

__Course objectives.__ By the end of the course, you should have a broad understanding of the various notions used in computational complexity theory to classify computational problems as hard or easy to solve. You are expected to become familiar with the important complexity classes, how they are related to each other, typical problems in those classes, and some of the central open problems in the field. You should be able to follow the proofs, and develop a feel for the techniques used in reasoning about computational complexity. The course will also briefly introduce you to applications of complexity theory to cryptography.

__Course contents.__ The course will mostly follow (a subset of) the material in the textbook. Additional reading material, when required, will be given out in class. Slides from the lectures and homework assignments will appear in this webpage.

__Work involved.__ Read the textbook (relevant sections); attend the lectures; read and ponder over references/handouts given in class. Grading will be based on assignments (60%), one class-test (15%), one reading-project (20%) and class-participation (5%). Assignments will typically be given out on a Wednesday and will be due in class after two weeks.

__Prerequisites.__ This is a graduate course, aimed at Computer Science, ECE and Mathematics students with an interest in theoretical computer science. Some familiarity with basic theory of computation, and some mathematical maturity will be expected.

__Office hours.__ **Thursday 2:00 -- 3:00 PM**. Please do come for the office hours if you find anything mysterious (or missed anything) in the lectures, class-tests or assignments. You are also welcome to drop by and chat about the content/structure of the course during the office hours. Feel free to send me e-mails anytime if you have any questions or comments.

Class Test: You can resubmit your class-test as a take-home assignment by Wednesday, May 5. No collaboration or external references are permitted. You are required to collect it back and resubmit it after self-evaluation by Monday, May 10.

Reading Project: Here is a list of suggested topics. A project report (6 to 10 pages) is due by Sunday, May 9.

- Lecture 00 [ pdf | print] (Jan 20): Introduction
- Lecture 01
[ pdf |
print]
(Jan 22): Time complexity, DTIME, NTIME, coNTIME. P, NP, co-NP. EXP, NEXP, co-NEXP. Reducing Search to Decision.
**[chapters: 1 & 2, except 2.2-2.4]** - Lecture 02
[ pdf |
print]
(Jan 27): NP-completeness.
**[sections: 2.2-2.4]** - Assignment 1: Released Jan 27. Due Feb 10.
- Lecture 03
[ pdf |
print]
(Jan 29): Time-hierarchy theorems.
**[chapter: 3]** - Lecture 04
[ pdf |
print]
(Feb 03): Ladner's Theorem, Limits of Diagonalization. Space complexity
**[sections: 3.3, 3.4, 4.1]** - Lecture 05
[ pdf |
print]
(Feb 05): Savitch's Theorem. PSPACE completeness.
**[sections: 4.1-4.2]** - Lecture 06
[ pdf |
print]
(Feb 10): NL completeness. NL=co-NL.
**[section: 4.3]** - Assignment 2: Released Feb 10. Due Feb 24.
- Lecture 07
[ pdf |
print]
(Feb 12): Polynomial Hierarchy
**[sections: 5.1, 5.2]** - Lecture 08
[ pdf |
print]
(Feb 17): Polynomial Hierarchy: Oracle-based Definitions
**[section: 5.5]** - Lecture 09
[ pdf |
print]
(Feb 19): Alternating Turing Machines
**[section: 5.3-5.4]** - Lecture 10
[ pdf |
print]
(Feb 24): Non-uniform Complexity
**[sections: 6.1, 6.3-6.7.1]** - Assignment 3: Released Feb 24. Due Mar 10.
- Lecture 11
[ pdf |
print]
Feb 26): Uniform Circuit Complexity: NC
^{i}, AC^{i}**[chapter: 6]** - Lecture 12
[ pdf |
print]
(Mar 03): Probabilistic Computation
**[chapter: 7]** - Lecture 13
[ pdf |
print]
(Mar 05): Probabilistic Computation
**[chapter: 7]** - Lecture 14
[ pdf |
print]
(Mar 10): Probabilistic Computation
**[chapter: 7]** - Assignment 4: Released Mar 10. Due March 31.
- Lecture 15
[ pdf |
print]
(Mar 12): Randomness Extraction
**[see section: 21.5]** - Lecture 16
[ pdf |
print]
(Mar 17): Interactive Proofs
**[chapter: 8]** - Lecture 17
[ pdf |
print]
(Mar 19): Interactive Proofs: IP=PSPACE
**[section: 8.3]**

---- Spring Break ----

- Lecture 18 [ pdf | print] (Mar 31): Interactive Proofs: AM
- Lecture 19 [ pdf | print] (Apr 02): Interactive Proofs: And beyond
- Assignment 5: Released April 7. Due April 28.
- Lecture 20
[ pdf |
print]
(Apr 07): PCP and Hardness of Approximation
**[chapter 11]** - Lecture 21
[ pdf |
print]
(Apr 09): Complexity of Counting
**[chapter 17]** - Class Test (Apr 14).
- Lecture 22
[ pdf |
print]
(Apr 16): Complexity of Counting: Toda's Theorem
**[section 17.4]** - Lecture 23
[ pdf |
print]
(Apr 21): Decision Trees
**[chapter 12]** - Lecture 24
[ pdf |
print]
(Apr 23): Communication Complexity
**[chapter 13]** - Lecture 25
[ pdf |
print]
(Apr 28): Circuit Lower-bounds
**[chapter 14]** - Assignment 6: Released April 28. Due May 7.
- Lecture 26
[ pdf |
print]
(Apr 30): Natural Proofs
**[chapter 23]** - Lecture 27
[ pdf |
print]
(May 05): Quantum computation
**[chapter 10]**