CS359: Hardness of Approximation

Instructor: Tim Roughgarden (Gates 462)

Time/location: 11AM-12:15 PM on Mondays and Wednesdays (and occasional Fridays) in Gates 100.

Course description: Results on and proof techniques for ruling out good approximation algorithms for NP-hard optimization problems. Topics: the PCP theorem; unique games conjecture; explicit expander graph constructions; applications to covering, graph, cut, network design, and satisfiability optimization problems; relevant techniques from Fourier analysis and error-correcting codes. Prerequisites: CS154 and CS261, or comparable mathematical maturity.


Primary reference:

Esteban Arcaute's notes:

Further general references:

Detailed schedule and references: