DIMACS TR: 2010-02
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
Authors: Prahladh Harsha and Moses Charikar
ABSTRACT
These are the lecture notes for the DIMACS Tutorial Limits
of Approximation Algorithms:
PCPs and Unique Games held at the DIMACS Center, CoRE Building,
Rutgers University
on 20-21 July, 2009. This tutorial was jointly sponsored by the DIMACS
Special Focus on
Hardness of Approximation, the DIMACS Special Focus on Algorithmic
Foundations of the
Internet, and the Center for Computational Intractability with support
from the National
Security Agency and the National Science Foundation.
The speakers at the tutorial were Matthew Andrews, Sanjeev Arora,
Moses Charikar,
Prahladh Harsha, Subhash Khot, Dana Moshkovitz and Lisa Zhang. The scribes were
Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan,
Alexander S. Kulikov,
Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard and Gwen
Spencer.
Paper Available at:
http://dimacs.rutgers.edu/archive/TechnicalReports/TechReports/2010/2010-02.pdf
DIMACS Home Page