Title: Near Linear Lower Bound for Dimension Reduction in L_1
Speaker: Ofer Neiman, Princeton University
Date: Wednesday, March 9, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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.