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.
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
10% Blog posts
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.
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.