*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Essie Reynolds
Summary Sentence: SCS Faculty Recruiting Seminar - Alexandr Andoni - Algorithmic Design via Efficient Data Representations
Full Summary: No summary paragraph submitted.
Alexandr Andoni
School of Computer Science
Faculty Recruiting Seminar
Alexandr Andoni, PhD
Visiting Scientist
University of California, Berkeley
Thursday, February 19, 2015 @ 11 A.M.
School of Computer Science
Klaus Classroom 2447
266 Ferst Dr
Atlanta GA 30332
(Light refreshments provided)
Algorithmic Design via Efficient Data Representations
Abstract: The growing scale of data demands novel algorithmic design frameworks that are able to handle modern datasets. In this talk, I will describe how such frameworks emerge from the methods of efficient data representations. The first illustration will be the Nearest Neighbor Search (NNS) problem --- an ubiquitous massive datasets problem that is of key importance in machine learning and other areas. Its goal is to preprocess a dataset of objects (e.g., images), so that later, given a new query object, one can efficiently return the object most similar to the query. Efficient solutions may be achieved via Locality Sensitive Hashing (LSH), a data representation method that has seen a lot of success in both theory and practice. I will present the best possible LSH-based algorithm for NNS under the Euclidean distance. Then, I will show a new method that, for the first time, provably outperforms the LSH-based algorithms. Taking a broader perspective, I will describe other examples where the lens of "efficient data representation" leads to new efficient algorithms. These examples include fast algorithms for estimating the edit distance and the Earth-Mover Distance, as well as a new algorithmic framework for parallel models of computation (such as MapReduce).
Bio: Alexandr Andoni is a computer scientist focused on advancing algorithmic foundations of massive data. His research interests broadly revolve around sublinear algorithms, high-dimensional geometry, and theoretical machine learning. Alexandr graduated from MIT in 2009, with a PhD thesis on Nearest Neighbor Search, under the supervision of Piotr Indyk. During 2009--2010, he was a postdoc at the Center for Computational Intractability at Princeton, as well as a visitor at NYU and IAS. Alexandr then joined Microsoft Research Silicon Valley, where he was a researcher until 2014. Currently, Alexandr is a visiting scientist at the Simons Institute for the Theory of Computing at UC Berkeley.
