Publications

This is our catalog of publications authored by IBM researchers, in collaboration with the global research community. It’s an ever-growing body of work that shows why IBM is one of the most important contributors to modern computing.

Date

Start

End

Featured collections

Popular topics

30 results for Robert Krauthgamer

Private approximation of NP-hard functions
- - Shai Halevi
  - Robert Krauthgamer
  - et al.
- 2001
- STOC 2001
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 ₁
- - 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