Meeting: Tuesdays and Thursdays, 1:30pm-2:50pm, NSH 1305
Instructors: Venkatesan
Guruswami, Ryan
O'Donnell
TA: Eric Blais
Course Blog: http://cmu-complexity.blogspot.com.
Office hours:
Eric: Tues. 12:30-1:30, Wean 3709.
Venkat and Ryan: By appointment.
Assignments: (problems and solutions available on request)
13% Homework 1
13% Homework 2
13% Homework 3
13% Homework 4
13% Homework 5
25% Midterm
10% Blog posts
Homework Policy:
Homework solutions must be typeset;
LaTeX is strongly preferred.
The following files provide a sample homework solution: .tex,
.bib, .sty, and
.pdf.
Collaboration is fine for the homeworks, but
you must do all the writeups yourself and list your collaborators.
Collaboration is not allowed for the midterm or blog posts.
Course Outline:
Lecture 01 -- The big questions
Lecture 02 -- Basic time classes
Lecture 03 -- Randomized time classes
Lecture 04 -- The polynomial time hierarchy
Lecture 05 -- Valiant-Vazirani Theorem and
approximate counting
Lecture 06 -- The BCGKT Theorem
Lecture 07 -- #P and Toda's Theorem
Lecture 08 -- Basics of space classes; Savitch,
TQBF, Immerman-Szelepcs?yi
Lecture 09 -- Circuits, NC, and branching
programs
Lecture 10 -- Barrington's Theorem, Lipton-Viglas
Theorem
Lecture 11 -- Interactive proofs, and IP =
PSPACE
Lecture 12 -- AM and MA
Lecture 13 -- Razborov-Smolensky circuit lower bound
for Parity
Lecture 14 -- The Switching
Lemma
Lecture 15 -- Hastad's lower bound for Parity;
Linial-Mansour-Nisan Theorem
Lecture 16 -- Nisan's pseudorandom generator for
small space
Lecture 17 -- The Nisan-Wigderson pseudorandom
generator
Lecture 18 -- Hardness vs. Randomness
Lecture 19 -- Impagliazzo's Hard-Core Set
Theorem
Lecture 20 -- Coding theory basics
Lecture 21 -- Sudan-Trevisan-Vadhan proof of the
Impagliazzo-Wigderson Theorem
Lecture 22 -- Derandomization implies circuit lower
bounds
Lecture 23 -- Impagliazzo-Kabanets-Wigderson and
Kabanets-Impagliazzo Theorems
Lecture 24 -- Expander
graphs
Lecture 25 -- Property testing
Lecture 26 -- Proof complexity
Lecture 27 -- SL = L
Lecture 28 -- Relativization, Natural Proofs, and
results that overcome them
Reading Materials: There is no textbook for the course, but
there are many sources we recommend you check out:
Computational
Complexity: A Modern Approach, by Arora and Barak (free).
Lectures in Computational
Complexity, by Cai (free).
Computational
Complexity: A Conceptual Perspective, by Goldreich (free drafts).
Computational
Complexity, by Papadimitriou.
van
Melkebeek's lecture notes.
Beame's
lecture
notes.
Miltersen's lecture
notes.
Umans's
lecture notes.
H?tad's
lecture notes.
Bogdanov's lecture
notes.
Sudan's lecture notes.
Trevisan's
lecture notes.
Spielman's
lecture notes.
M. Naor's
lecture notes.
Jaikumar's
lecture notes.
Rudich's
lecture notes.
Various notes
of Chakrabarti.