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.