Robert Krauthgamer

Bing Citeseer DBLP Google Google Scholar Kosmix Wikipedia Yahoo!
Loading Google Thumbnails...
2011
76Min-Max Graph Partitioning and Small Set Expansion. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz. CoRR (abs/1110.4319) (2011). Web SearchBibTeXDownload
75Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer. CoRR (abs/1111.4470) (2011). Web SearchBibTeXDownload
74The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer. CoRR (abs/1112.0699) (2011). Web SearchBibTeXDownload
73Fault-Tolerant Spanners: Better and Simpler. Michael Dinitz, Robert Krauthgamer. CoRR (abs/1101.5753) (2011). Web SearchBibTeXDownload
72Streaming Algorithms via Precision Sampling. Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak. FOCS 2011, 363-372. Web SearchBibTeXDownload
71Min-max Graph Partitioning and Small Set Expansion. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz. FOCS 2011, 17-26. Web SearchBibTeXDownload
70Fault-tolerant spanners: better and simpler. Michael Dinitz, Robert Krauthgamer. PODC 2011, 169-178. Web SearchBibTeXDownload
69How Hard Is It to Approximate the Best Nash Equilibrium?. Elad Hazan, Robert Krauthgamer. SIAM J. Comput. (40): 79-91 (2011). Web SearchBibTeXDownload
68A Nonlinear Approach to Dimension Reduction. Lee-Ad Gottlieb, Robert Krauthgamer. SODA 2011, 888-899. Web SearchBibTeXDownload
67Directed spanners via flow-based linear programs. Michael Dinitz, Robert Krauthgamer. STOC 2011, 323-332. Web SearchBibTeXDownload
66Pricing commodities. Robert Krauthgamer, Aranyak Mehta, Atri Rudra. Theor. Comput. Sci. (412): 602-613 (2011). Web SearchBibTeXDownload
2010
65Proximity Algorithms for Nearly-Doubling Spaces. Lee-Ad Gottlieb, Robert Krauthgamer. APPROX-RANDOM 2010, 192-204. Web SearchBibTeXDownload
64Efficient Classification for Metric Data. Lee-Ad Gottlieb, Leonid Kontorovich, Robert Krauthgamer. COLT 2010, 433-440. Web SearchBibTeXDownload
63Directed Spanners via Flow-Based Linear Programs. Michael Dinitz, Robert Krauthgamer. CoRR (abs/1011.3701) (2010). Web SearchBibTeXDownload
62Vertex Sparsifiers: New Results from Old Techniques. Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar. CoRR (abs/1006.4586) (2010). Web SearchBibTeXDownload
61Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak. CoRR (abs/1005.4033) (2010). Web SearchBibTeXDownload
60Approximating Sparsest Cut in Graphs of Bounded Treewidth. Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra. CoRR (abs/1006.3970) (2010). Web SearchBibTeXDownload
59Streaming Algorithms from Precision Sampling. Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak. CoRR (abs/1011.1263) (2010). Web SearchBibTeXDownload
58The Computational Hardness of Estimating Edit Distance. Alexandr Andoni, Robert Krauthgamer. SIAM J. Comput. (39): 2398-2429 (2010). Web SearchBibTeXDownload
2009
57A Nonlinear Approach to Dimension Reduction. Lee-Ad Gottlieb, Robert Krauthgamer. CoRR (abs/0907.5477) (2009). Web SearchBibTeXDownload
56Improved Lower Bounds for Embeddings intoL1$. Robert Krauthgamer, Yuval Rabani. SIAM J. Comput. (38): 2487-2498 (2009). Web SearchBibTeXDownload
55Partitioning graphs into balanced components. Robert Krauthgamer, Joseph Naor, Roy Schwartz. SODA 2009, 942-949. Web SearchBibTeXDownload
54Approximate line nearest neighbor in high dimensions. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen. SODA 2009, 293-301. Web SearchBibTeXDownload
53Overcoming the l1 non-embeddability barrier: algorithms for product metrics. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer. SODA 2009, 865-874. Cited by 14Web SearchBibTeXDownload
52How hard is it to approximate the best Nash equilibrium?. Elad Hazan, Robert Krauthgamer. SODA 2009, 720-727. Web SearchBibTeXDownload
2008
51Minimum Bisection. Robert Krauthgamer. Encyclopedia of Algorithms 2008. Web SearchBibTeXDownload
50The Smoothed Complexity of Edit Distance. Alexandr Andoni, Robert Krauthgamer. ICALP (1) 2008, 357-369. Web SearchBibTeXDownload
49Greedy List Intersection. Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, Atri Rudra. ICDE 2008, 1033-1042. Web SearchBibTeXDownload
48Earth mover distance over high-dimensional spaces. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer. SODA 2008, 343-352. Cited by 7Web SearchBibTeXDownload
47Metric clustering via consistent labeling. Robert Krauthgamer, Tim Roughgarden. SODA 2008, 809-818. Web SearchBibTeXDownload
2007
46The intrinsic dimensionality of graphs. Robert Krauthgamer, James R. Lee. Combinatorica (27): 551-585 (2007). Web SearchBibTeXDownload
45Earth Mover Distance over High-Dimensional Spaces. Alexandr Andoni, Piotr Indyk, Robert Krauthgamer. Electronic Colloquium on Computational Complexity (ECCC) (14) (2007). Web SearchBibTeXDownload
44The Computational Hardness of Estimating Edit Distance [Extended Abstract]. Alexandr Andoni, Robert Krauthgamer. FOCS 2007, 724-734. Web SearchBibTeXDownload
43Integrality Ratio for Group Steiner Trees and Directed Steiner Trees. Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang. SIAM J. Comput. (36): 1494-1511 (2007). Web SearchBibTeXDownload
42Estimating the sortedness of a data stream. Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar. SODA 2007, 318-327. Web SearchBibTeXDownload
41On triangulation of simple networks. Robert Krauthgamer. SPAA 2007, 8-15. Web SearchBibTeXDownload
40Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations. Robert Krauthgamer, Aranyak Mehta, Atri Rudra. WAOA 2007, 1-14. Web SearchBibTeXDownload
2006
39On the Hardness of Approximating Multicut and Sparsest-Cut. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar. Computational Complexity (15): 94-114 (2006). Cited by 74Web SearchBibTeXDownload
38Algorithms on negatively curved spaces. Robert Krauthgamer, James R. Lee. FOCS 2006, 119-132. Web SearchBibTeXDownload
37Improved lower bounds for embeddings into L1. Robert Krauthgamer, Yuval Rabani. SODA 2006, 1010-1017. Web SearchBibTeXDownload
36Embedding the Ulam metric into l1. Moses Charikar, Robert Krauthgamer. Theory of Computing (2): 207-224 (2006). Web SearchBibTeXDownload
2005
35On the Hardness of Approximating Multicut and Sparsest-Cut. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar. IEEE Conference on Computational Complexity 2005, 144-153. Cited by 74Web SearchBibTeXDownload
34Asymmetric k-center is log* n-hard to approximate. Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor. J. ACM (52): 538-551 (2005). Cited by 27Web SearchBibTeXDownload
33The black-box complexity of nearest-neighbor search. Robert Krauthgamer, James R. Lee. Theor. Comput. Sci. (348): 262-276 (2005). Web SearchBibTeXDownload
2004
32The Sketching Complexity of Pattern Matching. Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar. APPROX-RANDOM 2004, 261-272. Web SearchBibTeXDownload
31Measured descent: A new embedding method for finite metrics. Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor. CoRR (abs/cs/0412008) (2004). Web SearchBibTeXDownload
30Metric Embeddings--Beyond One-Dimensional Distortion. Robert Krauthgamer, Nathan Linial, Avner Magen. Discrete & Computational Geometry (31): 339-356 (2004). Web SearchBibTeXDownload
29Measured Descent: A New Embedding Method for Finite Metrics. Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor. FOCS 2004, 434-443. Web SearchBibTeXDownload
28Approximating Edit Distance Efficiently. Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar. FOCS 2004, 550-559. Web SearchBibTeXDownload
27The Black-Box Complexity of Nearest Neighbor Search. Robert Krauthgamer, James R. Lee. ICALP 2004, 858-869. Web SearchBibTeXDownload
26Hardness of Approximation for Vertex-Connectivity Network Design Problems. Guy Kortsarz, Robert Krauthgamer, James R. Lee. SIAM J. Comput. (33): 704-720 (2004). Web SearchBibTeXDownload
25Navigating nets: simple algorithms for proximity search. Robert Krauthgamer, James R. Lee. SODA 2004, 798-807. Web SearchBibTeXDownload
24Approximate classification via earthmover metrics. Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos. SODA 2004, 1079-1087. Web SearchBibTeXDownload
23Object location in realistic networks. Kirsten Hildrum, Robert Krauthgamer, John Kubiatowicz. SPAA 2004, 25-35. Web SearchBibTeXDownload
2003
22On Cutting a Few Vertices from a Graph. Uriel Feige, Robert Krauthgamer, Kobbi Nissim. Discrete Applied Mathematics (127): 643-649 (2003). Web SearchBibTeXDownload
21Tight lower bounds for the asymmetric k-center problem. Eran Halperin, Guy Kortsarz, Robert Krauthgamer. Electronic Colloquium on Computational Complexity (ECCC) (10) (2003). Web SearchBibTeXDownload
20Bounded Geometries, Fractals, and Low-Distortion Embeddings. Anupam Gupta, Robert Krauthgamer, James R. Lee. FOCS 2003, 534-543. Web SearchBibTeXDownload
19Detecting protein sequence conservation via metric embeddings. Eran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover. ISMB (Supplement of Bioinformatics) 2003, 122-129. Web SearchBibTeXDownload
18The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set. Uriel Feige, Robert Krauthgamer. SIAM J. Comput. (32): 345-370 (2003). Web SearchBibTeXDownload
17Integrality ratio for group Steiner trees and directed steiner trees. Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang. SODA 2003, 275-284. Web SearchBibTeXDownload
16Property testing of data dimensionality. Robert Krauthgamer, Ori Sasson. SODA 2003, 18-27. Web SearchBibTeXDownload
15Polylogarithmic inapproximability. Eran Halperin, Robert Krauthgamer. STOC 2003, 585-594. Web SearchBibTeXDownload
14The intrinsic dimensionality of graphs. Robert Krauthgamer, James R. Lee. STOC 2003, 438-447. Web SearchBibTeXDownload
13Constant factor approximation of vertex-cuts in planar graphs. Eyal Amir, Robert Krauthgamer, Satish Rao. STOC 2003, 90-99. Web SearchBibTeXDownload
2002
12Hardness of Approximation for Vertex-Connectivity Network-Design Problems. Guy Kortsarz, Robert Krauthgamer, James R. Lee. APPROX 2002, 185-199. Web SearchBibTeXDownload
11A Polylogarithmic Approximation of the Minimum Bisection. Uriel Feige, Robert Krauthgamer. SIAM J. Comput. (31): 1090-1118 (2002). Web SearchBibTeXDownload
2001
10On Approximating the Achromatic Number. Guy Kortsarz, Robert Krauthgamer. SIAM J. Discrete Math. (14): 408-422 (2001). Web SearchBibTeXDownload
9On approximating the achromatic number. Guy Kortsarz, Robert Krauthgamer. SODA 2001, 309-318. Web SearchBibTeXDownload
8Private approximation of NP-hard functions. Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim. STOC 2001, 550-559. Web SearchBibTeXDownload
7Online server allocation in a server farm via benefit task systems. T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko. STOC 2001, 540-549. Web SearchBibTeXDownload
2000
6Networks on Which Hot-Potato Routing Does Not Livelock. Uriel Feige, Robert Krauthgamer. Distributed Computing (13): 53-58 (2000). Web SearchBibTeXDownload
5A polylogarithmic approximation of the minimum bisection. Uriel Feige, Robert Krauthgamer. FOCS 2000, 105-115. Web SearchBibTeXDownload
4Finding and certifying a large hidden clique in a semirandom graph. Uriel Feige, Robert Krauthgamer. Random Struct. Algorithms (16): 195-208 (2000). Web SearchBibTeX
3Improved classification via connectivity information. Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher. SODA 2000, 576-585. Web SearchBibTeXDownload
2Approximating the minimum bisection size (extended abstract). Uriel Feige, Robert Krauthgamer, Kobbi Nissim. STOC 2000, 530-536. Web SearchBibTeXDownload
1997
1Stereoscopic families of permutations, and their applications. Uriel Feige, Robert Krauthgamer. ISTCS 1997, 85-95. Web SearchBibTeXDownload
from DBLP and Google Scholar
Developed by the Database Group at the University of Wisconsin and Yahoo! Research