### DIMACS Theoretical Computer Science Seminar

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.