Approximability of Optimization Problems
A complexity-theoretic view of combinatorial optimization.
Prereq: 6.042, 6.045, 6.046.
Instructor: Madhu Sudan
Time: MW 2:30-4:00pm
3-0-9 H-Level Grad Credit
I'll be adding material here as we go along. For now here
are some sources for approximation algorithms;
and hardness of approximations.
Topics covered so far:
For future scribes, here is a
sample file and
the preamble.tex file that
Lecture 1 (9/8):
Introduction to NP,
NP Optimization, Approximation. Brief History.
Lecture 2 (9/13):
Approximation algorithms for TSP, Vertex Cover,
and Knapsack. Fully Polynomial Time Approximation Schemes
(FPTAS) and Strong NP-Completeness.
Lecture 3 (9/15):
LP and IP (in constant # of variables).
Minimizing Makespan. PTAS for Minimizing Makespan.
Lecture 4 (9/20):
4/3-approximation of MAX SAT. Vertex Cover revisited;
Half-integrality of the LP formulation; Consequences.
Lecture 5 (9/22):
Guest Lecture by
Approximations via the Primal-Dual method.
Lecture 6 (9/27):
Set Cover. Minimum Multicut (and metric relaxations).
Lecture 7 (9/29):
Minimum Multicut (contd.). Opening negative results.
Approximation preserving reductions. Gap Problems.
Lecture 8 (10/4):
Gap Problems. The necessity of probabilistic proof systems.
Brief history of probabilistic proof systems: IP, MIP, OIP,
Lecture 9 (10/6):
PCP and the Hardness of Approximations. Max Clique, Max 3SAT.
Lecture 10 (10/13):
Tools for PCP: Error correcting codes.
Reed-Solomon codes (univariate polynomials);
Reed-Muller codes (multivariate polynomials);
Hadamard codes (linear polynomials).
Codes via concatenation.
Lecture 11 (10/20):
Tools for PCP: Self-correction algorithms.
Self-correctors for Hadamard and multivariate
polynomials. Self-correction with a prover.
Lecture 12 (10/25):
Tools for PCP: Self-testing algorithms.
A Self-tester for Hadamard codes: The Blum-Luby-Rubinfeld test for
Lecture 13 (10/27):
Linearity testing (contd.):
Fourier transforms and the linearity test.
Lecture 14 (11/1):
Low Degree Testing: Testing on axis-parallel lines,
Testing via random lines; Properties of random lines.
Lecture 15 (11/3):
Low Degree Testing: The lines vs. points test for
multivariate polynomials. Reduction to testing
bivariate polynomials on axis parallel lines.
Lecture 16 (11/8):
Low Degree Testing: Testing bivariate polynomials.
Lecture 17 (11/10):
PCP via Hadamard codes: An exponential sized PCP for NP.
PCP via polynomials; The Constraint satisfaction problem
Lecture 18 (11/15):
Hardness of the constraint satisfaction problem for polynomials.
Lecture 19 (11/17):
A 3-prover 1-round proof system for NP.
Composition of proof systems: Outer verifier and Inner verifiers.
Lecture 20 (11/22):
Composition of proof systems. Proof of the PCP theorem.
Lecture 21 (11/24):
Current versions of the PCP theorem. Parallel repetition and
improved outer verifiers. Hastad's inner verifier.
Lecture 22 (11/29):
Back to hardness of approximations: Gadget construction.
Lecture 23 (12/1):
Tailormade PCPs: Zero-knowledge and the chromatic number.
Lecture 24 (12/6):
MIPs and hardness of approximation: Set Cover.
Lecture 25 (12/8):