Advertising Console

    [Metric 2011] Moses Charikar

    Reposter
    Nicolas Schabanel

    par Nicolas Schabanel

    26
    233 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, 13:30-14:30
    Moses Charikar (Princeton U.)
    A Near Linear Lower Bound for Dimension Reduction in L1
    -------
    Given a set of n points in L1, how many dimensions are needed to
    represent all pairwise distances within a specific distortion ? This
    dimension-distortion tradeoff question is well understood for the L2
    norm, where O(log n)/eps2) dimensions suffice to achieve 1+eps
    distortion. In sharp contrast, there is a significant gap between
    upper and lower bounds for dimension reduction in L1. In this work,
    we show the first near linear lower bounds for dimension reduction in
    L1. In particular, we show that 1+eps distortion requires at least
    n^{1-O(1/log(1/eps))} dimensions.

    Our proofs are combinatorial, but inspired by linear programming. In
    fact, our techniques lead to a simple combinatorial argument that is
    equivalent to the LP based proof of Brinkman-Charikar for lower bounds
    on dimension reduction in L1.

    Joint work with Alex Andoni, Ofer Neiman and Huy Nguyen.