The computational hardness of estimating edit distance
- Alexandr Andoni
- Robert Krauthgamer
- 2007
- FOCS 2007
Publications
Date
Featured collections
Popular topics
30 results for Robert Krauthgamer
On triangulation of simple networks
- Robert Krauthgamer
- 2007
- SPAA 2007
Estimating the sortedness of a data stream
- Parikshit Gopalan
- T.S. Jayram
- et al.
- 2007
- SODA 2007
Integrality ratio for group steiner trees and directed Steiner trees
- Eran Halperin
- Guy Kortsarz
- et al.
- 2006
- SIAM Journal on Computing
Algorithms on negatively curved spaces
- Robert Krauthgamer
- Jmes R. Lee
- 2006
- FOCS 2006
On the hardness of approximating multicut and sparsest-cut
- Shuchi Chawla
- Robert Krauthgamer
- et al.
- 2006
- Computational Complexity
A polylogarithmic approximation of the minimum bisection
- Uriel Feige
- Robert Krauthgamer
- 2006
- SIAM Review
Improved lower bounds for embeddings into L1
- Robert Krauthgamer
- Yuval Rabani
- 2006
- SODA 2006
The black-box complexity of nearest-neighbor search
- Robert Krauthgamer
- James R. Lee
- 2005
- Theoretical Computer Science
Asymmetric K-center Is log* H-hard to approximate
- Julia Chuzhoy
- Sudipto Guha
- et al.
- 2005
- Journal of the ACM