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