- Arora-Barak
- (Contribute suggestions/errata. You'll need to login first.)

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

- CS 579/ECE 579/MATH 578: Spring 2008
- Prof. Manoj M. Prabhakaran
- 11:00 AM to 12:15 PM Tuesday/Thursday
- 1302 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 (75%), one class-test (20%) and class-participation (5%). Assignments will typically be given out on a Tuesday and will be due in class after two weeks.
No office hours on April 11th. Assignment 4 is now due on Tuesday April 22.

__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.__ **Fridays 3:30-4:30**. 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.

- Lecture 00 [anim | pdf | print] (Jan 15): Introduction
- Lecture 01
[anim |
pdf |
print]
(Jan 17): 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
[anim |
pdf |
print]
(Jan 22): NP-completeness.
**[sections: 2.2-2.4]** - Assignment 1, part 1: Released Jan 22. Due Jan 31.
- Lecture 03
[anim |
pdf |
print]
(Jan 24): Time-hierarchy theorems, Ladner's Theorem.
**[chapter: 3]** - Lecture 04
[anim |
pdf |
print]
(Jan 29): Limits of Diagonalization. Space complexity: Space Hierarchy, Savitch's Theorem
**[sections: 3.2, 3.5, 4.1-4.2, 4.3.1]** - Assignment 1, part 2: Released Jan 29. Due Feb 7.
- Lecture 05
[anim |
pdf |
print]
(Jan 31): PSPACE completeness, NL completeness.
**[section: 4.3]** - Lecture 06
[anim |
pdf |
print]
(Feb 5): NL completeness. NL=co-NL.
**[section: 4.4]** - Lecture 07
[anim |
pdf |
print]
(Feb 7): Polynomial Hierarchy
**[sections: 5.1, 5.2.1]** - Lecture 08
[anim |
pdf |
print]
(Feb 12): Polynomial Hierarchy: Oracle-based Definitions
**[section: 5.5]** - Lecture 09
[anim |
pdf |
print]
(Feb 14): Alternating Turing Machines
**[section: 5.3-5.4]** - Lecture 10
[anim |
pdf |
print]
(Feb 19): Non-uniform Complexity
**[sections: 6.1-6.5.1]** - Assignment 2: Released Feb 21. Due Mar 6.
- Lecture 11
[anim |
pdf |
print]
Feb 21): Uniform Circuit Complexity: NC
^{i}, AC^{i}**[chapter: 6 (and some more)]** - Lecture 12
[anim |
pdf |
print]
(Feb 26): Probabilistic Computation
**[chapter: 7]** - Lecture 13
[anim |
pdf |
print]
(Feb 28): Probabilistic Computation
**[chapter: 7]** - Lecture 14
[anim |
pdf |
print]
(Mar 4): Probabilistic Computation
**[chapter: 7]** - Lecture 15 [anim | pdf | print] (Mar 6): Randomness Extraction
- Assignment 3: Released Mar 6. Due March 25.
- Lecture 16
[anim |
pdf |
print]
(Mar 11): Interactive Proofs
**[chapter: 8]** - Lecture 17
[anim |
pdf |
print]
(Mar 13): Interactive Proofs: IP=PSPACE
**[section: 8.5]** - Lecture 18 [anim | pdf | print] (Mar 25): Interactive Proofs: AM
- Class Test (Mar 27).
- Lecture 19
[anim |
pdf |
print]
(Apr 01): Interactive Proofs: And beyond
**[sections 8.7-8.8]** - Lecture 20
[anim |
pdf |
print]
(Apr 03): Complexity of Counting
**[chapter 9]** - Assignment 4: Released April 3. Due April 22.
- Lecture 21
[anim |
pdf |
print]
(Apr 08): Complexity of Counting: Toda's Theorem
**[section 9.3]** - Lecture 22
[anim |
pdf |
print]
(Apr 10): Decision Trees
**[chapter 11]** - Lecture 23
[anim |
pdf |
print]
(Apr 15): Communication Complexity
**[chapter 12]** - Lecture 24
[anim |
pdf |
print]
(Apr 17): Circuit Lower-bounds
**[chapter 13]** - Lecture 25
[anim |
pdf |
print]
(Apr 22): Natural Proofs
**[chapter 22]** - Assignment 5: Released April 23. Due May 2.
__No collaboration on this assignment!__ - Lecture 26
[anim |
pdf |
print]
(Apr 24): PCP and Hardness of Approximation
**[chapter 18]** - Lecture 27
[anim |
pdf |
print]
(Apr 29): Quantum computation
**[chapter 20]**