CS 151: Complexity Theory (Spring
2004)
Some material on this page has been updated in the most recent
version of this course, which can be found here.
Instructor: Chris Umans
Office: Jorgensen 286
Times: Tu/Th 10:30-12:00 in 125 Steele
TA: David Soloveichik
Office hours:
- Tuesdays 1-2 in Jorgensen 286, and by appointment (Chris)
- Wednesdays 5-6 in Moore 204 (David)
Announcements:
- I have packets of graded material and final grades available for pick-up. Have a great summer!
- On problem 4 of the midterm, the hint should refer to problem 3 of Problem Set 3 rather than problem 4.
- The third problem of Problem Set 4 is optional. You may solve it for extra credit.
Handouts:
Lecture Slides:
- Lecture 1: languages, complexity classes, Turing Machines, reductions and
completeness (ppt, pdf)
- Lecture 2: time and space classes, hierarchy theorems, relationships between classes, P- + EXP-complete problems (ppt, pdf)
- Lecture 3: nondeterminism, NTIME hierarchy theorem, Ladner's Theorem (ppt, pdf)
- Lecture 4: sparse languages and NP, nondeterministic space classes, s-t-connectivity, Savitch's Theorem, I-S Theorem (ppt, pdf)
- Lecture 5: circuits, uniformity and advice, NC hierarchy, formula lower bound on the Andreev function (ppt, pdf)
- Lecture 6: Razborov's lower bound on monotone circuits for CLIQUE (ppt, pdf)
- Lecture 7: communication complexity, Schwartz-Zippel Lemma, Valiant-Vazirani Theorem, randomized complexity classes, Adelman's Theorem (ppt, pdf)
- Lecture 8: pseudo-random generators and derandomization, Goldreich-Levin hard bit, Yao's Lemma, BMY generator (ppt, pdf)
- Lecture 9: Nisan-Wigderson pseudo-random generator, error-correcting codes from polynomials (ppt, pdf)
- Lecture 10: Decoding Reed-Muller codes, transforming worst-case hardness into average-case hardness, extractors (ppt, pdf)
- Lecture 11: Trevisan Extractor, strong error reduction for BPP, RL, the Polynomial-Time Hierarchy (ppt, pdf)
- Lecture 12: the Polynomial-Time Hierarchy, complete problems for levels of PH and PSPACE (ppt, pdf)
- Lecture 13: natural complete problems for levels of PH and PSPACE, interactive proofs, graph nonisomorphism (ppt, pdf)
- Lecture 14: Karp-Lipton Theorem, BPP in PH, the power of IP (ppt, pdf)
- Lecture 15: IP=PSPACE, Arthur-Merlin Games, AM and MA, approximation algorithms (ppt, pdf)
- Lecture 16: gap-producing and gap-preserving reductions, Probabilistically Checkable Proofs, elements of the proof of the PCP Theorem (ppt, pdf)
- Lecture 17: #P, relativization, natural proofs, course summary (ppt, pdf)
Problem Sets:
- Problem Set 1: (ps, pdf)
Solutions (ps, pdf)
- Problem Set 2: (ps, pdf)
Solutions (ps, pdf)
- Problem Set 3: (ps, pdf)
Solutions (ps, pdf)
- Problem Set 4: (ps, pdf)
Solutions (ps, pdf)
- Midterm: (ps, pdf)
Solutions (ps, pdf)
- Problem Set 5: (ps, pdf)
Solutions (ps, pdf)
- Problem Set 6: (ps, pdf)
Solutions (ps, pdf)
- Problem Set 7: (ps, pdf)
Solutions (ps, pdf)
- Final: (ps, pdf)
Solutions (ps, pdf)