[Colloquium] Talks at TTIC: Alexandr Andoni, Simons Institute, Berkeley

[Dawn Ellis]

When:     Friday, April 17th at 11am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Alexandr Andoni, Simons Institute, Berkeley

Title:       Algorithmic design via efficient data representations

Abstract:

Modern datasets are at scales that would be unthinkable just a decade
ago. This demands rethinking the principles of algorithmic design used
to handle such datasets. In this talk, I will describe how such
principles 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.  A central technique for
tackling this problem is 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 also describe how the lens of
"efficient data representation" leads to new fast algorithms for other
longstanding questions. Specifically, I will discuss a classic dynamic
programming problem (edit distance) and a Linear Programming problem
(earth-mover distance). Finally, I will briefly mention how the above
ideas enable an algorithmic framework for parallel computation systems
such as MapReduce.

Host:  Julia Chuzhoy,  cjulia at ttic.edu

-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150410/8bcb79fa/attachment-0001.htm