TA: Carol Wang
Lectures: TR 3-4:30pm, GHC 4102
Office hours: Thursday 4:30pm (Steven, GHC 7219) and Monday 4pm (Carol, GHC 7515), or by appointment
The midterm is graded. The mean score was 66/100 points.
Problem set 0 (pdf) was given out September 10 and was due September 17th. The mean score was just under 10/15 points.
Problem set 1 (pdf) was given out September 17 and was due on October 1. The mean score was 32.5/50 points.
Problem set 2 (pdf) was given out on October 1 and was due on October 15. The mean score was 29/50 points.
Problem set 3 (pdf) was given out on October 15 and was due on October 29. The mean score was 33/46 points.
Problem set 4 (pdf) was given out on November 5 and was due on November 19. Notes on extractors for the AM/MA problem are here.
Problem set 5 (pdf) was given out on November 19th and is due on December 3.
Lecture 1 (ppt) was on the big questions of complexity.
Lecture 2 (pptx) was on the Turing machine model and diagonalisation.
Lectures 3-4 (pptx) were on non-determinism (NP, NEXP) and lazy diagonalisation (the non-deterministic time hierarchy theorem and Ladner's theorem).
Lecture 5 (pptx) was on non-deterministic space (NPSPACE=PSPACE, NL=co-NL). Note these slides have been revised from the ones presented in class.
Lecture 6 (pptx) was on circuits and complexity inside P (NL, SC, NC).
Lecture 7 (pptx) was on the polynomial hierarchy and PSPACE (alternation, Karp-Lipton, BPP in PH).
Lectures 8-9 (pptx) were on randomised classes, communication complexity, and Valiant-Vazirani (the complexity of unique solutions).
Lecture 10 (pptx) was on the complexity of counting (sharp-P).
Lectures 11-12 (pptx) were on interactive protocols (IP (aka PSPACE), MA, AM).
Lectures 13-14 (pptx) were on pseudorandom generators (PRGs) and Goldreich-Levin.
Grading will be based on problem sets (40%) and take-home midterm and final (30% each). Your lowest problem set score will be dropped at the end of the semester.
The textbook for this course is Arora and Barak's Computational Complexity. (Link goes to an online draft, in case you don't have a copy. Any page/chapter references will come from the published version, though.)