- 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 2011
- Prof. Manoj M. Prabhakaran
- 11:00 AM to 12:15 PM Tuesday/Thursday
- 1111 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.

Here is a list of suggested topics for the reading project.

__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 Tuesday or Thursday 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.__ **Wednesday 2:00-3:00PM**. 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.

__Collaboration Policy.__ Limited collaboration is allowed for assignments, unless otherwise specified: you can discuss the problems with others in the class, but you should write up your solutions independently. In particular, you should not look at solutions written up by others. All collaboration should be declared.

Class Test: On Tuesday, March 29 (in class). The topics include what was covered up to (and including) Lecture 14. You are allowed to refer to the lecture notes during the exam, but no other reference, collaboration or assistance should be used.

There will be no office hour on Wednesday, March 30.

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

---- Spring Break ----

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