Publications

30 results for Robert Krauthgamer

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