Algorithms and Complexity Seminar
Near Linear Lower Bound for Dimension Reduction in L_1
Ofer Neiman (Princeton University)
Given a set of n points in L_1, how many dimensions are needed to
represent all pairwise distances within a specific distortion ?
This dimension-distortion tradeoff question is well understood for the
L_2 norm, where O((\log n)/\epsilon^{2}) dimensions suffice to achieve
1+\epsilon distortion. In sharp contrast, there is a significant gap between
upper and lower bounds for dimension reduction in L_1.
In this work, we show the first near linear lower bounds for dimension
reduction in L_1. In particular, we show that 1+\epsilon distortion
requires at least n^{1-O(1/\log(1/\epsilon))} 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
L_1.
Joint work with Alex Andoni, Moses Charikar and Huy Nguyen.