<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 12 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";
color:black;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:"Consolas","serif";
color:black;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Arial","sans-serif";
color:blue;
font-weight:normal;
font-style:normal;
text-decoration:none none;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body bgcolor=white lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='color:blue'>Huy Nguyen will present his research seminar/general exam on Thursday <o:p></o:p></span></p><p class=MsoNormal><span style='color:blue'>May 5 at 2PM in Room 302. The members of his committee are Sanjeev <o:p></o:p></span></p><p class=MsoNormal><span style='color:blue'>Arora (advisor), Moses Charikar, and Bernard Chazelle. Everyone is <o:p></o:p></span></p><p class=MsoNormal><span style='color:blue'>invited to attend his talk and those faculty wishing to remain for the oral <o:p></o:p></span></p><p class=MsoNormal><span style='color:blue'>exam following are welcome to do so. His abstract and reading list follow <o:p></o:p></span></p><p class=MsoNormal><span style='color:blue'>below.<o:p></o:p></span></p><p class=MsoNormal><span style='color:blue'>------------------------------<o:p></o:p></span></p><p class=MsoNormal>Abstract<br><br>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<sup>2</sup>)} 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. <br><br>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}.<br><br>This is joint work with Alexandr Andoni, Moses Charikar, and Ofer Neiman.<br><br>Reading list<br><br>Book<br><br>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009.<br><br>Papers<br><br>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 <br><br>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. <br><br>Bo Brinkman and Moses Charikar. 2005. On the impossibility of dimension reduction in l1. J. ACM 52, 5 (September 2005), 766-788. <br><br>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 <br><br>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 <br><br>Piotr Indyk. On Approximate Nearest Neighbors under l[infinity] Norm, Journal of Computer and System Sciences, Volume 63, Issue 4, December 2001 <br><br>Piotr Indyk. 2006. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53, 3 (May 2006), 307-323. <br><br>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 <br><br>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. <br><br>Rafail Ostrovsky, Yuval Rabani. Low distortion embedding for edit distance, Preliminary version appeared in STOC '05. Full version JACM, 2008. <br><br><o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>