- 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 2007
- Prof. Manoj M. Prabhakaran
- 11:00 AM to 12:15 PM Tuesday/Thursday
- 1111 Siebel Center
- Credit: 4 hours
- TA: Mike Rosulek, 3301 SC

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%), easy/short class-tests (20%) and class-participation (5%). Assignments will typically be given out on a Tuesday and will be due in class after two weeks. Class-tests will be announced a week in advance.

__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.__ Prof. Prabhakaran's office hours are Thursdays 1:30-3:00pm, every week (unless otherwise announced in class). TA Mike Rosulek's office hours are Mondays 1-2:30pm. Please do come for the office hours if you found 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 us e-mails anytime if you have any questions or comments.

- Lecture 00 (Jan 16): Introduction
- Lecture 01
[anim |
print]
(Jan 18): 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 |
print]
(Jan 23): NP-completeness.
**[sections: 2.2-2.4]** - Assignment 1, part 1: Released Jan 23. Due Feb 1.
- Lecture 03
[anim |
print]
(Jan 25): Time-hierarchy theorems, Ladner's Theorem.
**[chapter: 3]** - Lecture 04
[anim |
print]
(Jan 30): 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 30. Due Feb 8.
- Lecture 05
[anim |
print]
(Feb 1): PSPACE completeness, NL completeness.
**[sections: 4.3-4.4.1]** - Lecture 06
[anim |
print]
(Feb 6): NL=co-NL. Starting Polynomial Hierarchy: Quantifier-based definition
**[section: 4.4.2, 5.1]** - Lecture 07
[anim |
print]
(Feb 8): Polynomial Hierarchy: Collapse results, Oracle-based definition
**[sections: 5.2.1, 5.5]** **Feb 13 class canceled due to snow!**- Lecture 08
[anim |
print]
(Feb 15): Polynomial Hierarchy: Alternation
**[sections: 5.3-5.4]** **Review**(Feb 20)**Class Test 1**(Feb 22) download: in-class, makeup- Lecture 09
[anim |
print]
(Feb 27): Non-uniform Complexity
**[sections: 6.1-6.5.1]** - Assignment 2: Released Mar 1. Due Mar 13 and 16.
- Lecture 10
[anim |
print]
(Mar 1): Uniform Circuit Complexity: NC
^{i}, AC^{i}**[chapter: 6 (and some more)]** - Lecture 11
[anim |
print]
(Mar 6): Probabilistic Computation
**[chapter: 7]** - Lecture 12
[anim |
print]
(Mar 8): Probabilistic Computation
**[chapter: 7]** - Lecture 13
[anim |
print]
(Mar 13): Probabilistic Computation
**[chapter: 7]** - Lecture 14 [anim | print] (Mar 15): Randomness Extraction
- Assignment 3: Released Mar 17. Due April 10.
- Lecture 15
[anim |
print]
(Mar 27): Interactive Proofs
**[chapter: 8]** - Lecture 16
[anim |
print]
(Mar 29): Interactive Proofs: IP=PSPACE
**[section: 8.5]** - Lecture 17 [anim | print] (Apr 03): Interactive Proofs: AM
- Lecture 18
[anim |
print]
(Apr 05): Interactive Proofs: And beyond
**[sections 8.7-8.8]** - Lecture 19
[anim |
print]
(Apr 10): Complexity of Counting
**[chapter 9]** - Lecture 20
[anim |
print]
(Apr 12): Complexity of Counting: Toda's Theorem
**[section 9.3]** - Assignment 4: Released April 14. Due April 30.
- Lecture 21
[anim |
print]
(Apr 17): Decision Trees
**[chapter 11]** - Lecture 22
[anim |
print]
(Apr 19): Communication Complexity
**[chapter 12]** - Lecture 23
[anim |
print]
(Apr 24): Circuit Lower-bounds
**[chapter 13]** - Lecture 24
[anim |
print]
(Apr 26): Natural Proofs
**[chapter 22]** - Assignment 5: Released April 30. Due May 10.
__No collaboration on this assignment!__ - Lecture 25
[anim |
print]
(May 1): PCP and Hardness of Approximation
**[chapter 18]**