Huy Nguyen will present his research seminar/general exam on Thursday

May 5 at 2PM in Room 302.  The members of his committee are Sanjeev

Arora (advisor), Moses Charikar, and Bernard Chazelle.  Everyone is

invited to attend his talk and those faculty wishing to remain for the oral

exam following are welcome to do so.  His abstract and reading list follow

below.

------------------------------

Abstract

Given a set of n points in \ell_{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 \ell_{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 \ell_{1}. A recent result shows that distortion 1+\epsilon can be achieved with O(n/\epsilon^{2}) dimensions. On the other hand, the only lower bounds known are that distortion \delta requires n^{\Omega(1/\delta²)} dimension and that distortion 1+\epsilon requires n^{1/2-O(\epsilon \log(1/\epsilon))} dimensions. In this work, we show the first near linear lower bounds for dimension reduction in \ell_{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 \ell_{1}.

This is joint work with Alexandr Andoni, Moses Charikar, and Ofer Neiman.

Reading list

Book

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009.

Papers

Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David Woodruff. "Efficient Sketches for Earth-Mover Distance, with Applications," Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on , vol., no., pp.324-330, 25-27 Oct. 2009

Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. 2008. Earth mover distance over high-dimensional spaces. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '08). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 343-352.

Bo Brinkman and Moses Charikar. 2005. On the impossibility of dimension reduction in l1. J. ACM 52, 5 (September 2005), 766-788.

Moses Charikar, Amit Sahai, "Dimension Reduction in the \ell _1 Norm," Foundations of Computer Science, Annual IEEE Symposium on, p. 551, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002

Sariel Har-Peled, "A Replacement for Voronoi Diagrams of Near Linear Size," Foundations of Computer Science, Annual IEEE Symposium on, p. 94, 42nd IEEE symposium on Foundations of Computer Science (FOCS'01), 2001

Piotr Indyk. On Approximate Nearest Neighbors under l[infinity] Norm, Journal of Computer and System Sciences, Volume 63, Issue 4, December 2001

Piotr Indyk. 2006. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53, 3 (May 2006), 307-323.

James R. Lee, Assaf Naor, Embedding the diamond graph in L_p and dimension reduction in L_1. Geometric And Functional Analysis, Volume 14, Number 4, 745-747, DOI: 10.1007/s00039-004-0473-8

James R. Lee, Manor Mendel, Assaf Naor, Metric structures in L1: dimension, snowflakes, and average distortion, European Journal of Combinatorics, Volume 26, Issue 8, November 2005, Pages 1180-1190, ISSN 0195-6698, DOI: 10.1016/j.ejc.2004.07.002.

Rafail Ostrovsky, Yuval Rabani. Low distortion embedding for edit distance, Preliminary version appeared in STOC '05. Full version JACM, 2008.