BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Algorithmic design via efficient data representati
 ons
DTSTART:20150309T101500
DTEND:20150309T113000
DTSTAMP:20260406T172848Z
UID:ef98c0acc9d97cfafb01ab4e3c54c978d6151c8fa23a1587633812f1
CATEGORIES:Conferences - Seminars
DESCRIPTION:By : Alexandr Andoni - UC Berkeley\nIC Faculty candidateAbstra
 ct :\nModern datasets are at scales that would be unthinkable just a decad
 e ago. This demands rethinking the principles of algorithmic design used t
 o handle such datasets. In this talk\, I will describe how such principles
  emerge from the methods of efficient data representations.\nThe first ill
 ustration will be the Nearest Neighbor Search (NNS) problem -- an ubiquito
 us massive datasets problem that is of key importance in machine learning 
 and other areas.  A central technique for tackling this problem is Locali
 ty Sensitive Hashing (LSH)\, a data representation method that has seen a 
 lot of success in both theory and practice. I will present the best possib
 le LSH-based algorithm for NNS under the Euclidean distance. Then\, I will
  show a new method that\, for the first time\, provably outperforms the LS
 H-based algorithms.\nTaking a broader perspective\, I will also describe h
 ow the lens of "efficient data representation" leads to new fast algorithm
 s for other longstanding questions. Specifically\, I will discuss a classi
 c dynamic programming problem (edit distance) and a Linear Programming pro
 blem (earth-mover distance). Finally\, I will briefly mention how the abov
 e ideas enable an algorithmic framework for parallel computation systems s
 uch as MapReduce.Bio :\nAlexandr 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\, w
 ith a PhD thesis on Nearest Neighbor Search\, under the supervision of Pio
 tr Indyk. During 2009--2010\, he was a postdoc at the Center for Computati
 onal Intractability at Princeton\, as well as a visitor at NYU and IAS. Al
 exandr then joined Microsoft Research Silicon Valley\, where he was a rese
 archer until 2014. Currently\, Alexandr is a visiting scientist at the Sim
 ons Institute for the Theory of Computing at UC Berkeley.More information
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR