Advertising Console

    [Metric 2011] Ryan O'Donnell 1

    Nicolas Schabanel

    par Nicolas Schabanel

    367 vues
    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

    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.