Approximability of Optimization Problems
A complexitytheoretic view of combinatorial optimization.
Prereq: 6.042, 6.045, 6.046.
Instructor: Madhu Sudan
Time: MW 2:304:00pm
Location: 24307
309 HLevel Grad Credit
Homepage:
http://theory.lcs.mit.edu/~madhu/FT99/course.html
Course announcement
References
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:

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 NPCompleteness.

Lecture 3 (9/15):
LP and IP (in constant # of variables).
Minimizing Makespan. PTAS for Minimizing Makespan.

Lecture 4 (9/20):
4/3approximation of MAX SAT. Vertex Cover revisited;
Halfintegrality of the LP formulation; Consequences.

Lecture 5 (9/22):
Guest Lecture by
Michel Goemans:
Approximations via the PrimalDual 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,
PCP.

Lecture 9 (10/6):
PCP and the Hardness of Approximations. Max Clique, Max 3SAT.

Lecture 10 (10/13):
Tools for PCP: Error correcting codes.
ReedSolomon codes (univariate polynomials);
ReedMuller codes (multivariate polynomials);
Hadamard codes (linear polynomials).
Codes via concatenation.

Lecture 11 (10/20):
Tools for PCP: Selfcorrection algorithms.
Selfcorrectors for Hadamard and multivariate
polynomials. Selfcorrection with a prover.

Lecture 12 (10/25):
Tools for PCP: Selftesting algorithms.
A Selftester for Hadamard codes: The BlumLubyRubinfeld test for
linearity.

Lecture 13 (10/27):
Linearity testing (contd.):
Fourier transforms and the linearity test.

Lecture 14 (11/1):
Low Degree Testing: Testing on axisparallel 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
for polynomials.

Lecture 18 (11/15):
Hardness of the constraint satisfaction problem for polynomials.

Lecture 19 (11/17):
A 3prover 1round 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: Zeroknowledge and the chromatic number.

Lecture 24 (12/6):
MIPs and hardness of approximation: Set Cover.

Lecture 25 (12/8):
Concluding thoughts.
For future scribes, here is a
sample file and
the preamble.tex file that
it uses.