CSE 564
Complexity of Combinatorial Problems
Graduate Course
CSE 564
Complexity of combinatorial problems through the lens of intractability, randomness, interaction, and lower bounds.
1. Course Description
This graduate course studies computational complexity from a modern viewpoint centered on intractability. Starting with hard problems such as satisfiability, the course asks how computational difficulty should be measured and how the power of computation changes once we add resources such as randomness, alternation, and interaction.
Topics include complexity classes, randomized computation, interactive proofs, the theorem IP = PSPACE, probabilistically checkable proofs, hardness of approximation, and selected themes in circuit complexity. The exact emphasis can shift with the interests of the class and available time.
What the course emphasizes
- Foundational proof techniques in complexity theory
- Connections between randomness, interaction, and verification
- Modern examples of lower bounds and hardness phenomena
Course format
- Lecture-driven discussions
- Reading from textbook chapters and selected papers
- A final project based on independent reading
2. Reading Material
Primary text
[AB] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach.
Additional references
- [W] Avi Wigderson, Mathematics and Computation
- [O'D] Ryan O'Donnell, Analysis of Boolean Functions
- Irit Dinur, History of PCP
- Oded Goldreich, Low-degree testing note
- Hastad's paper on optimal inapproximability results for MAX-3XOR and related problems
3. Syllabus Table and Lecture Notes
The schedule below is based on the current Canvas syllabus and is intended as a working plan.
| Date | Topic | Reading | Notes |
|---|---|---|---|
| Jan 13 | Review of Turing machines, diagonalization, time hierarchy theorem | AB 1-3 | |
| Jan 15 | Ladner's theorem and the relativizing barrier | AB 3 | Note |
| Jan 20 | Polynomial hierarchy | AB 5 | Note |
| Jan 22 | Interactive proofs and graph non-isomorphism in IP | AB 8 | |
| Jan 27 | AM[k] = AM, graph non-isomorphism in AM, and IP[k] subsets of AM[k+2] | AB 8 | Note |
| Jan 29 | Sum-check protocol | AB 8 | Note |
| Feb 3 | IP = PSPACE and counting classes | AB 17 | |
| Feb 5 | Toda's theorem | AB 17 | Note |
| Feb 10 | PCP and hardness of approximation | AB 17, AB 22 | |
| Feb 12 | Hadamard-based PCP | AB 22 | Note |
| Feb 17 | Linearity test and combinatorial proof | ||
| Feb 19 | Linearity test and Fourier-analytic proof | O'D 1 | Note |
| Feb 24 | Polynomial-size PCP | Note | |
| Feb 26 | Low-degree test | Goldreich's note | Note |
| Mar 3 | Hastad's inapproximability result for MAX-3XOR | Hastad's paper | |
| Mar 5 | MAX-3XOR inapproximability, continuation | Note |
Lecture Notes
Project expectation
Students are expected to work toward a final reading-based project that synthesizes one theme from the course with an outside paper or set of notes.