[Metric 2011] Ryan O'Donnell 1

-------
METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
-------
Workshop on Metric embeddings, algorithms  and hardness of approximation
January 17-21, 2011
-------
Jan 17, 10:30-11:30
Ryan O'Donnell (Carnegie Mellon U.)
Inapproximability: A How-To Guide 1/3

In this mini-course, I will introduce the area of approximability of
optimization problems and then discuss the methods used to prove
inapproximability results. We will assume the hardness of Label-Cover
and Unique-Games - these problems will be discussed in other
mini-courses.

Key tools include the discrete Fourier transform and the notion of
"influences" for Boolean functions. As case studies, we will discuss
the Max-k-Coverage, Max-3Lin, and Max-Cut problems.