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.