Private approximation of NP-hard functions
- Shai Halevi
- Robert Krauthgamer
- et al.
- 2001
- STOC 2001
Publications
Date
Featured collections
Popular topics
30 results for Robert Krauthgamer
On the hardness of approximating multicut and sparsest-cut
- Shuchi Chawla
- Robert Krauthgamer
- et al.
- 2006
- Computational Complexity
Min-max graph partitioning and small set expansion
- Nikhil Bansal
- Uriel Feige
- et al.
- 2014
- SIAM Journal on Computing
Improved lower bounds for embeddings into l 1
- Robert Krauthgamer
- Yuval Rabani
- 2009
- SIAM Journal on Computing
The intrinsic dimensionality of graphs
- Robert Krauthgamer
- James R. Lee
- 2008
- Combinatorica
Integrality ratio for group steiner trees and directed Steiner trees
- Eran Halperin
- Guy Kortsarz
- et al.
- 2006
- SIAM Journal on Computing
A polylogarithmic approximation of the minimum bisection
- Uriel Feige
- Robert Krauthgamer
- 2006
- SIAM Review
The black-box complexity of nearest-neighbor search
- Robert Krauthgamer
- James R. Lee
- 2005
- Theoretical Computer Science
Measured descent: A new embedding method for finite metrics
- R. Krauthgamer
- J.R. Lee
- et al.
- 2005
- Geometric and Functional Analysis
Hardness of approximation for vertex-connectivity network design problems
- Guy Kortsarz
- Robert Krauthgamer
- et al.
- 2004
- SIAM Journal on Computing