February 15, Tuesday
12:00 – 13:30
Near Linear Lower Bound for Dimension Reduction in L_1
Computer Science seminar
Lecturer : Ofer Neiman
Affiliation : Department of Computer Science, Princeton University
Location : 202\37
Host : Prof. Michael Elkin
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