15-855*: An Intensive Introduction to Computational Complexity Theory

Spring 2009, 12 units

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.