 | 2009 |
|---|
| 56 |       | Alexandr Andoni,
Piotr Indyk,
Robert Krauthgamer,
Huy L. Nguyen:
Approximate line nearest neighbor in high dimensions.
SODA 2009: 293-301 |
| 55 | | Elad Hazan,
Robert Krauthgamer:
How hard is it to approximate the best Nash equilibrium?
SODA 2009: 720-727 |
| 54 | | Alexandr Andoni,
Piotr Indyk,
Robert Krauthgamer:
Overcoming the l1 non-embeddability barrier: algorithms for product metrics.
SODA 2009: 865-874 |
| 53 | | Robert Krauthgamer,
Joseph Naor,
Roy Schwartz:
Partitioning graphs into balanced components.
SODA 2009: 942-949 |
| 52 | | Lee-Ad Gottlieb,
Robert Krauthgamer:
A Nonlinear Approach to Dimension Reduction
CoRR abs/0907.5477: (2009) |
| 51 | | Robert Krauthgamer,
Yuval Rabani:
Improved Lower Bounds for Embeddings intoL1$.
SIAM J. Comput. 38(6): 2487-2498 (2009) |
| 2008 |
|---|
| 50 | | Alexandr Andoni,
Robert Krauthgamer:
The Smoothed Complexity of Edit Distance.
ICALP (1) 2008: 357-369 |
| 49 | | Robert Krauthgamer,
Aranyak Mehta,
Vijayshankar Raman,
Atri Rudra:
Greedy List Intersection.
ICDE 2008: 1033-1042 |
| 48 | | Alexandr Andoni,
Piotr Indyk,
Robert Krauthgamer:
Earth mover distance over high-dimensional spaces.
SODA 2008: 343-352 |
| 47 | | Robert Krauthgamer,
Tim Roughgarden:
Metric clustering via consistent labeling.
SODA 2008: 809-818 |
| 46 | | Robert Krauthgamer:
Minimum Bisection.
Encyclopedia of Algorithms 2008 |
| 2007 |
|---|
| 45 | | Alexandr Andoni,
Robert Krauthgamer:
The Computational Hardness of Estimating Edit Distance [Extended Abstract].
FOCS 2007: 724-734 |
| 44 | | Parikshit Gopalan,
T. S. Jayram,
Robert Krauthgamer,
Ravi Kumar:
Estimating the sortedness of a data stream.
SODA 2007: 318-327 |
| 43 | | Robert Krauthgamer:
On triangulation of simple networks.
SPAA 2007: 8-15 |
| 42 | | Robert Krauthgamer,
Aranyak Mehta,
Atri Rudra:
Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations.
WAOA 2007: 1-14 |
| 41 | | Alexandr Andoni,
Piotr Indyk,
Robert Krauthgamer:
Earth Mover Distance over High-Dimensional Spaces.
Electronic Colloquium on Computational Complexity (ECCC) 14(048): (2007) |
| 40 | | Eran Halperin,
Guy Kortsarz,
Robert Krauthgamer,
Aravind Srinivasan,
Nan Wang:
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees.
SIAM J. Comput. 36(5): 1494-1511 (2007) |
| 2006 |
|---|
| 39 | | Robert Krauthgamer,
James R. Lee:
Algorithms on negatively curved spaces.
FOCS 2006: 119-132 |
| 38 | | Robert Krauthgamer,
Yuval Rabani:
Improved lower bounds for embeddings into L1.
SODA 2006: 1010-1017 |
| 37 | | Shuchi Chawla,
Robert Krauthgamer,
Ravi Kumar,
Yuval Rabani,
D. Sivakumar:
On the Hardness of Approximating Multicut and Sparsest-Cut.
Computational Complexity 15(2): 94-114 (2006) |
| 36 | | Moses Charikar,
Robert Krauthgamer:
Embedding the Ulam metric into l1.
Theory of Computing 2(1): 207-224 (2006) |
| 2005 |
|---|
| 35 | | Shuchi Chawla,
Robert Krauthgamer,
Ravi Kumar,
Yuval Rabani,
D. Sivakumar:
On the Hardness of Approximating Multicut and Sparsest-Cut.
IEEE Conference on Computational Complexity 2005: 144-153 |
| 34 | | Julia Chuzhoy,
Sudipto Guha,
Eran Halperin,
Sanjeev Khanna,
Guy Kortsarz,
Robert Krauthgamer,
Joseph Naor:
Asymmetric k-center is log* n-hard to approximate.
J. ACM 52(4): 538-551 (2005) |
| 33 | | Robert Krauthgamer,
James R. Lee:
The black-box complexity of nearest-neighbor search.
Theor. Comput. Sci. 348(2-3): 262-276 (2005) |
| 2004 |
|---|
| 32 | | Ziv Bar-Yossef,
T. S. Jayram,
Robert Krauthgamer,
Ravi Kumar:
The Sketching Complexity of Pattern Matching.
APPROX-RANDOM 2004: 261-272 |
| 31 | | Robert Krauthgamer,
James R. Lee,
Manor Mendel,
Assaf Naor:
Measured Descent: A New Embedding Method for Finite Metrics.
FOCS 2004: 434-443 |
| 30 | | Ziv Bar-Yossef,
T. S. Jayram,
Robert Krauthgamer,
Ravi Kumar:
Approximating Edit Distance Efficiently.
FOCS 2004: 550-559 |
| 29 | | Robert Krauthgamer,
James R. Lee:
The Black-Box Complexity of Nearest Neighbor Search.
ICALP 2004: 858-869 |
| 28 | | Aaron Archer,
Jittat Fakcharoenphol,
Chris Harrelson,
Robert Krauthgamer,
Kunal Talwar,
Éva Tardos:
Approximate classification via earthmover metrics.
SODA 2004: 1079-1087 |
| 27 | | Robert Krauthgamer,
James R. Lee:
Navigating nets: simple algorithms for proximity search.
SODA 2004: 798-807 |
| 26 | | Kirsten Hildrum,
Robert Krauthgamer,
John Kubiatowicz:
Object location in realistic networks.
SPAA 2004: 25-35 |
| 25 | | Robert Krauthgamer,
James R. Lee,
Manor Mendel,
Assaf Naor:
Measured descent: A new embedding method for finite metrics
CoRR abs/cs/0412008: (2004) |
| 24 | | Robert Krauthgamer,
Nathan Linial,
Avner Magen:
Metric Embeddings--Beyond One-Dimensional Distortion.
Discrete & Computational Geometry 31(3): 339-356 (2004) |
| 23 | | Guy Kortsarz,
Robert Krauthgamer,
James R. Lee:
Hardness of Approximation for Vertex-Connectivity Network Design Problems.
SIAM J. Comput. 33(3): 704-720 (2004) |
| 2003 |
|---|
| 22 | | Anupam Gupta,
Robert Krauthgamer,
James R. Lee:
Bounded Geometries, Fractals, and Low-Distortion Embeddings.
FOCS 2003: 534-543 |
| 21 | | Eran Halperin,
Jeremy Buhler,
Richard M. Karp,
Robert Krauthgamer,
Ben Westover:
Detecting protein sequence conservation via metric embeddings.
ISMB (Supplement of Bioinformatics) 2003: 122-129 |
| 20 | | Robert Krauthgamer,
Ori Sasson:
Property testing of data dimensionality.
SODA 2003: 18-27 |
| 19 | | Eran Halperin,
Guy Kortsarz,
Robert Krauthgamer,
Aravind Srinivasan,
Nan Wang:
Integrality ratio for group Steiner trees and directed steiner trees.
SODA 2003: 275-284 |
| 18 | | Robert Krauthgamer,
James R. Lee:
The intrinsic dimensionality of graphs.
STOC 2003: 438-447 |
| 17 | | Eran Halperin,
Robert Krauthgamer:
Polylogarithmic inapproximability.
STOC 2003: 585-594 |
| 16 | | Eyal Amir,
Robert Krauthgamer,
Satish Rao:
Constant factor approximation of vertex-cuts in planar graphs.
STOC 2003: 90-99 |
| 15 | | Uriel Feige,
Robert Krauthgamer,
Kobbi Nissim:
On Cutting a Few Vertices from a Graph.
Discrete Applied Mathematics 127(3): 643-649 (2003) |
| 14 | | Eran Halperin,
Guy Kortsarz,
Robert Krauthgamer:
Tight lower bounds for the asymmetric k-center problem
Electronic Colloquium on Computational Complexity (ECCC) 10(035): (2003) |
| 13 | | Uriel Feige,
Robert Krauthgamer:
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set.
SIAM J. Comput. 32(2): 345-370 (2003) |
| 2002 |
|---|
| 12 | | Guy Kortsarz,
Robert Krauthgamer,
James R. Lee:
Hardness of Approximation for Vertex-Connectivity Network-Design Problems.
APPROX 2002: 185-199 |
| 11 | | Uriel Feige,
Robert Krauthgamer:
A Polylogarithmic Approximation of the Minimum Bisection.
SIAM J. Comput. 31(4): 1090-1118 (2002) |
| 2001 |
|---|
| 10 | | Guy Kortsarz,
Robert Krauthgamer:
On approximating the achromatic number.
SODA 2001: 309-318 |
| 9 | | T. S. Jayram,
Tracy Kimbrel,
Robert Krauthgamer,
Baruch Schieber,
Maxim Sviridenko:
Online server allocation in a server farm via benefit task systems.
STOC 2001: 540-549 |
| 8 | | Shai Halevi,
Robert Krauthgamer,
Eyal Kushilevitz,
Kobbi Nissim:
Private approximation of NP-hard functions.
STOC 2001: 550-559 |
| 7 | | Guy Kortsarz,
Robert Krauthgamer:
On Approximating the Achromatic Number.
SIAM J. Discrete Math. 14(3): 408-422 (2001) |
| 2000 |
|---|
| 6 |  | Uriel Feige,
Robert Krauthgamer:
A polylogarithmic approximation of the minimum bisection.
FOCS 2000: 105-115 |
| 5 | | Andrei Z. Broder,
Robert Krauthgamer,
Michael Mitzenmacher:
Improved classification via connectivity information.
SODA 2000: 576-585 |
| 4 | | Uriel Feige,
Robert Krauthgamer,
Kobbi Nissim:
Approximating the minimum bisection size (extended abstract).
STOC 2000: 530-536 |
| 3 | | Uriel Feige,
Robert Krauthgamer:
Networks on Which Hot-Potato Routing Does Not Livelock.
Distributed Computing 13(1): 53-58 (2000) |
| 2 | | Uriel Feige,
Robert Krauthgamer:
Finding and certifying a large hidden clique in a semirandom graph.
Random Struct. Algorithms 16(2): 195-208 (2000) |
| 1997 |
|---|
| 1 | | Uriel Feige,
Robert Krauthgamer:
Stereoscopic families of permutations, and their applications.
ISTCS 1997: 85-95 |
