<div dir="ltr"><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif">When:     Wednesday, January 25th at 11:00 am </font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif"><br></font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif">Where:    <span class="gmail-m_-3415450340192868837gmail-il">TTIC</span>, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif"><br></font></div><div style="font-size:12.8px"><span style="font-size:12.8px">Who:       </span><span class="gmail-m_-3415450340192868837gmail-il" style="font-size:12.8px">Ilya</span><span style="font-size:12.8px"> Razenshteyn, MIT: CSAIL</span><br></div><div style="font-size:12.8px"><span style="font-size:12.8px"><br></span></div><div style="font-size:12.8px"><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div style="font-size:12.8px">Title:        New Algorithms for High-Dimensional Data</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><span class="gmail-m_-3415450340192868837gmail-m_2730288220849107527m_-7883959024691227618gmail-il">Abstract</span>: A popular approach in data analysis is to represent a dataset in a high-dimensional feature vector space, and reduce a given task to a geometric computational problem. As it turns out, the running times of most of the classic geometric algorithms suffer from an exponential dependence on the dimension and are typically not applicable to the high-dimensional regime. This necessitates the development of new algorithmic approaches that overcome this "curse of dimensionality". In this talk I will give an overview of my work in this area. In particular:</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">* I will describe new algorithms for the high-dimensional Nearest Neighbor Search (NNS) problem.  Our algorithms improve, for the first time, upon the popular Locality-Sensitive Hashing (LSH) approach. The main insight behind the new algorithms is the use of hash functions that are *data dependent*, i.e., , that are carefully tailored to a given dataset. In contrast, prior algorithms used generic, data-oblivious hash families.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">* Next, I will outline how to make the core component of the above algorithms---the optimal LSH for cosine distance---practical. This yields an implementation of LSH which is competitive with the state of the art heuristics for the NNS problem.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">* Finally, I will show how to determine the limits of distance-preserving data sketching, i.e., vector compression methods that approximately preserve the distances between vectors. In particular, I will show the first non-trivial lower bound for the sketching complexity of the well-studied Earth Mover Distance. </div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">The common theme that unifies these and other algorithms for high-dimensional data is the use of "efficient data representations": randomized hashing, sketching, dimensionality reduction, metric embeddings, and others. One goal of the talk is to describe a holistic view of all of these techniques.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Host: <a href="mailto:yury@ttic.edu" target="_blank">Yury Makarychev</a></div><div><br></div><div><br></div><div><br></div><div><br></div></div></div><div><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 504</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div>
</div>