Robert Krauthgamer
My research is concerned with the design and analysis of efficient
algorithms, and with the limitations thereof. I study a broad range of
computational problems, with primary focus on Data Analysis (e.g., near
neighbor searching and string processing) and on Combinatorial
Optimization (e.g., graph partitioning and maximum clique), but I am
also interested in algorithms for networking and for massive data sets.
Technically, a large part of my recent work explores algorithmic and
analytic aspects of finite metric spaces (e.g. high dimensional geometry).
Recent Publications
- [with Alexandr Andoni] The computational hardness of estimating edit distance. Proceedings of FOCS 2007, to appear.
- [with James R. Lee] Algorithms on negatively curved spaces. Proceedings of FOCS 2006.
- [with James R. Lee, Manor Mendel and Assaf Naor] Measured descent: A new embedding method for finite metrics. Geometric and Functional Analysis (GAFA) 15 (4): 839-858, 2005.