CSE 564

Complexity of Combinatorial Problems

Graduate Course

CSE 564

Complexity of combinatorial problems through the lens of intractability, randomness, interaction, and lower bounds.

Prerequisite CMPSC 464 · Assessment 30% attendance, 70% final project

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
[BS] Boaz Barak and David Steurer, Proofs, beliefs, and algorithms through the lens of sum-of-squares

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
Mar 17	Parallel repetition, part I	Holenstein's paper
Mar 19	Parallel repetition, part II
Mar 24	Parallel repetition, part III		Note
Mar 26	Goemans-Williamson algorithms		Note
Mar 31	Sum-of-Squares algorithms, intro	[BS] Ch. 1.2.
Apr 2	Degree-2 SoS algorithms and Grothendieck's inequality	[BS] Ch. 2.3.	Note
Apr 7	Rounding global correlation		Note
Apr 9	Sum-of-Squares lower bound, part I	[BS] Ch. 3.2.
Apr 14	Sum-of-Squares lower bound, part II	[BS] Ch. 3.2.
Apr 16	Unique games conjecture and max cut, part I
Apr 21	Unique games conjecture and max cut, part II		Note
Apr 23	Invariance principle		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.