dblp.uni-trier.dewww.uni-trier.de

Robert Krauthgamer Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
56EEAlexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen: Approximate line nearest neighbor in high dimensions. SODA 2009: 293-301
55EEElad Hazan, Robert Krauthgamer: How hard is it to approximate the best Nash equilibrium? SODA 2009: 720-727
54EEAlexandr Andoni, Piotr Indyk, Robert Krauthgamer: Overcoming the l1 non-embeddability barrier: algorithms for product metrics. SODA 2009: 865-874
53EERobert Krauthgamer, Joseph Naor, Roy Schwartz: Partitioning graphs into balanced components. SODA 2009: 942-949
52EELee-Ad Gottlieb, Robert Krauthgamer: A Nonlinear Approach to Dimension Reduction CoRR abs/0907.5477: (2009)
51EERobert Krauthgamer, Yuval Rabani: Improved Lower Bounds for Embeddings intoL1$. SIAM J. Comput. 38(6): 2487-2498 (2009)
2008
50EEAlexandr Andoni, Robert Krauthgamer: The Smoothed Complexity of Edit Distance. ICALP (1) 2008: 357-369
49EERobert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, Atri Rudra: Greedy List Intersection. ICDE 2008: 1033-1042
48EEAlexandr Andoni, Piotr Indyk, Robert Krauthgamer: Earth mover distance over high-dimensional spaces. SODA 2008: 343-352
47EERobert Krauthgamer, Tim Roughgarden: Metric clustering via consistent labeling. SODA 2008: 809-818
46EERobert Krauthgamer: Minimum Bisection. Encyclopedia of Algorithms 2008
2007
45EEAlexandr Andoni, Robert Krauthgamer: The Computational Hardness of Estimating Edit Distance [Extended Abstract]. FOCS 2007: 724-734
44EEParikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar: Estimating the sortedness of a data stream. SODA 2007: 318-327
43EERobert Krauthgamer: On triangulation of simple networks. SPAA 2007: 8-15
42EERobert Krauthgamer, Aranyak Mehta, Atri Rudra: Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations. WAOA 2007: 1-14
41EEAlexandr Andoni, Piotr Indyk, Robert Krauthgamer: Earth Mover Distance over High-Dimensional Spaces. Electronic Colloquium on Computational Complexity (ECCC) 14(048): (2007)
40EEEran 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
39EERobert Krauthgamer, James R. Lee: Algorithms on negatively curved spaces. FOCS 2006: 119-132
38EERobert Krauthgamer, Yuval Rabani: Improved lower bounds for embeddings into L1. SODA 2006: 1010-1017
37EEShuchi 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)
36EEMoses Charikar, Robert Krauthgamer: Embedding the Ulam metric into l1. Theory of Computing 2(1): 207-224 (2006)
2005
35EEShuchi 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
34EEJulia 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)
33EERobert Krauthgamer, James R. Lee: The black-box complexity of nearest-neighbor search. Theor. Comput. Sci. 348(2-3): 262-276 (2005)
2004
32EEZiv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar: The Sketching Complexity of Pattern Matching. APPROX-RANDOM 2004: 261-272
31EERobert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor: Measured Descent: A New Embedding Method for Finite Metrics. FOCS 2004: 434-443
30EEZiv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar: Approximating Edit Distance Efficiently. FOCS 2004: 550-559
29EERobert Krauthgamer, James R. Lee: The Black-Box Complexity of Nearest Neighbor Search. ICALP 2004: 858-869
28EEAaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos: Approximate classification via earthmover metrics. SODA 2004: 1079-1087
27EERobert Krauthgamer, James R. Lee: Navigating nets: simple algorithms for proximity search. SODA 2004: 798-807
26EEKirsten Hildrum, Robert Krauthgamer, John Kubiatowicz: Object location in realistic networks. SPAA 2004: 25-35
25EERobert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor: Measured descent: A new embedding method for finite metrics CoRR abs/cs/0412008: (2004)
24EERobert Krauthgamer, Nathan Linial, Avner Magen: Metric Embeddings--Beyond One-Dimensional Distortion. Discrete & Computational Geometry 31(3): 339-356 (2004)
23EEGuy Kortsarz, Robert Krauthgamer, James R. Lee: Hardness of Approximation for Vertex-Connectivity Network Design Problems. SIAM J. Comput. 33(3): 704-720 (2004)
2003
22EEAnupam Gupta, Robert Krauthgamer, James R. Lee: Bounded Geometries, Fractals, and Low-Distortion Embeddings. FOCS 2003: 534-543
21EEEran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover: Detecting protein sequence conservation via metric embeddings. ISMB (Supplement of Bioinformatics) 2003: 122-129
20EERobert Krauthgamer, Ori Sasson: Property testing of data dimensionality. SODA 2003: 18-27
19EEEran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang: Integrality ratio for group Steiner trees and directed steiner trees. SODA 2003: 275-284
18EERobert Krauthgamer, James R. Lee: The intrinsic dimensionality of graphs. STOC 2003: 438-447
17EEEran Halperin, Robert Krauthgamer: Polylogarithmic inapproximability. STOC 2003: 585-594
16EEEyal Amir, Robert Krauthgamer, Satish Rao: Constant factor approximation of vertex-cuts in planar graphs. STOC 2003: 90-99
15EEUriel Feige, Robert Krauthgamer, Kobbi Nissim: On Cutting a Few Vertices from a Graph. Discrete Applied Mathematics 127(3): 643-649 (2003)
14EEEran Halperin, Guy Kortsarz, Robert Krauthgamer: Tight lower bounds for the asymmetric k-center problem Electronic Colloquium on Computational Complexity (ECCC) 10(035): (2003)
13EEUriel 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
12EEGuy Kortsarz, Robert Krauthgamer, James R. Lee: Hardness of Approximation for Vertex-Connectivity Network-Design Problems. APPROX 2002: 185-199
11EEUriel Feige, Robert Krauthgamer: A Polylogarithmic Approximation of the Minimum Bisection. SIAM J. Comput. 31(4): 1090-1118 (2002)
2001
10EEGuy Kortsarz, Robert Krauthgamer: On approximating the achromatic number. SODA 2001: 309-318
9EET. 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
8EEShai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim: Private approximation of NP-hard functions. STOC 2001: 550-559
7EEGuy 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
5EEAndrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher: Improved classification via connectivity information. SODA 2000: 576-585
4EEUriel Feige, Robert Krauthgamer, Kobbi Nissim: Approximating the minimum bisection size (extended abstract). STOC 2000: 530-536
3EEUriel 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
1EEUriel Feige, Robert Krauthgamer: Stereoscopic families of permutations, and their applications. ISTCS 1997: 85-95

Coauthor Index

1Eyal Amir [16]
2Alexandr Andoni [41] [45] [48] [50] [54] [56]
3Aaron Archer [28]
4Ziv Bar-Yossef [30] [32]
5Andrei Z. Broder [5]
6Jeremy Buhler (Jeremy D. Buhler) [21]
7Moses Charikar [36]
8Shuchi Chawla [35] [37]
9Julia Chuzhoy [34]
10Jittat Fakcharoenphol [28]
11Uriel Feige [1] [2] [3] [4] [6] [11] [13] [15]
12Parikshit Gopalan [44]
13Lee-Ad Gottlieb [52]
14Sudipto Guha [34]
15Anupam Gupta [22]
16Shai Halevi [8]
17Eran Halperin [14] [17] [19] [21] [34] [40]
18Chris Harrelson [28]
19Elad Hazan [55]
20Kirsten Hildrum (Kris Hildrum) [26]
21Piotr Indyk [41] [48] [54] [56]
22T. S. Jayram (Jayram S. Thathachar) [9] [30] [32] [44]
23Richard M. Karp [21]
24Sanjeev Khanna [34]
25Tracy Kimbrel [9]
26Guy Kortsarz [7] [10] [12] [14] [19] [23] [34] [40]
27John Kubiatowicz [26]
28Ravi Kumar (S. Ravi Kumar) [30] [32] [35] [37] [44]
29Eyal Kushilevitz [8]
30James R. Lee [12] [18] [22] [23] [25] [27] [29] [31] [33] [39]
31Nathan Linial (Nati Linial) [24]
32Avner Magen [24]
33Aranyak Mehta [42] [49]
34Manor Mendel [25] [31]
35Michael Mitzenmacher [5]
36Assaf Naor [25] [31]
37Joseph Naor (Seffi Naor) [34] [53]
38Huy L. Nguyen [56]
39Kobbi Nissim [4] [8] [15]
40Yuval Rabani [35] [37] [38] [51]
41Vijayshankar Raman [49]
42Satish Rao [16]
43Tim Roughgarden [47]
44Atri Rudra [42] [49]
45Ori Sasson [20]
46Baruch Schieber [9]
47Roy Schwartz [53]
48D. Sivakumar [35] [37]
49Aravind Srinivasan [19] [40]
50Maxim Sviridenko [9]
51Kunal Talwar [28]
52Éva Tardos [28]
53Nan Wang [19] [40]
54Ben Westover [21]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)