[talks] H Nguyen general exam

[Melissa Lawson]

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/\delta2)} 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. 



 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20110502/592af6b5/attachment.html>