CSAIL Event Calendar: Previous Series

[A&C seminar] Near Linear Lower Bound for Dimension Reduction in L_1

Speaker: Ofer Neiman , Princeton University
Date: December 13 2010
Time: 4:00PM to 5:00PM
Location: G575
Contact: Aleksander Madry, madry@mit.edu
Relevant URL: http://people.csail.mit.edu/madry/algcompsem/

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.

See other events that are part of

See other events happening in December 2010