6.893 Preliminary course announcement

Prereq: 6.042, 6.045, 6.046.
Instructor: Madhu Sudan
Time: MW 2:30-4:00pm
Location: 24-307
3-0-9 H-Level Grad Credit
Homepage: http://theory.lcs.mit.edu/~madhu/FT99/course.html

Approximability of Optimization Problems

A complexity-theoretic view of combinatorial optimization.

Introduction: Combinatorial optimization. Complexity theory. P, NP, NP-completeness. Approximability as a performance measure. Examples of optmization problems and approximation algorithms.

Inapproximability: Constraint satisfaction problems. Proofs and optimization. Approximability and Probabilistically checkable proofs (PCPs). Interactive Proofs (IP) and Multiple-prover Interactive Proofs (MIPs). Parameters of interest. Hardness of Approximation from PCPs.

Constructions of PCPs: Connections with error-correcting codes. Constructions of error-correcting codes. Properties of low-degree polynomials. Linearity and low-degree testing.

Complexity issues: Gap problems. Complexity classes for optimization. Descriptive complexity and approximability. Reductions between optimization problems. Gap-preserving reductions. Linear reductions. Gadget reductions.

Current and future directions.