SCS Faculty Recruiting Seminar - Alexandr Andoni - Algorithmic Design via Efficient Data Representations

Event Details

Essie Reynolds


Summary Sentence: SCS Faculty Recruiting Seminar - Alexandr Andoni - Algorithmic Design via Efficient Data Representations

Full Summary: No summary paragraph submitted.

  • Alexandr Andoni 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.

Additional Information

In Campus Calendar

College of Computing, School of Computer Science

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Alexandr Andoni, College of Computing, School of Computer Science, SCS
  • Created By: Birney Robert
  • Workflow Status: Published
  • Created On: Feb 12, 2015 - 5:53am
  • Last Updated: Apr 13, 2017 - 5:20pm