[Metric 2011] Moses Charikar

-------
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.