• Calendar

December 25, Sunday
11:30 – 13:00

The plethora of data available nowadays has tremendous potential, but analyzing it presents a host of algorithmic challenges. Current data sets are mostly unstructured and noisy, requiring relatively complicated computational tasks, such as sequence alignment and similarity search. Furthermore, the data's enormous size might severely restrict the computational paradigm, e.g., to streaming or sublinear-time algorithms.

I will present some recent rigorous algorithmic approaches aimed at explaining and/or predicting success in practice. In particular, for problems that are hard in the worst-case, one may design a plausible model for real-life data, and then exploit this ``additional structure'' to devise improved algorithms. My running example will be near neighbor searching in regimes such as the Euclidean distance and the edit distance.

Bio: Robert Krauthgamer is a Research Staff Member at the IBM Almaden Research Center, working on the design and analysis of algorithms. Specific application areas include data analysis, combinatorial optimization, routing and peer-to-peer networks, with some recent emphasis on high-dimensional geometry and finite metric spaces.

Robert earned his PhD at the Weizmann Insitute of Science, under the supervision of Prof. Uri Feige, and after his graduation in 2001 he spent two years as a postdoc at UC Berkeley. His research won prestigious awards from the Weizmann Institute, SIAM (Society for Industrial and Applied Mathematics) and IBM Research.