Advertising Console

    [Metric 2011] Moses Charikar

    Nicolas Schabanel

    par Nicolas Schabanel

    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.