Publications of Robert Krauthgamer by keyword

Analysis of Algorithms ~ Computational Complexity ~ Metric Spaces and Embeddings ~ Web-related

Analysis of Algorithms

  1. Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern (AA, CC)
    Robert Krauthgamer and Ohad Trabelsi.
    Manuscript, August 2017.
    [abstract] [full version: arXiv]
  2. Refined Vertex Sparsifiers of Planar Graphs (AA, ME)
    Robert Krauthgamer and Inbal Rika.
    Manuscript, February 2017.
    [abstract] [full version: arXiv]
  3. Conditional Lower Bounds for All-Pairs Max-Flow (AA, CC)
    Robert Krauthgamer and Ohad Trabelsi.
    In ICALP 2017.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  4. Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order (AA, ME)
    Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, and Lin F. Yang.
    Manuscript, September 2016 (revised November 2017).
    [abstract] [full version: arXiv]
  5. Color-Distance Oracles and Snippets (AA, ME)
    Tsvi Kopelowitz, and Robert Krauthgamer.
    In Proceedings of CPM 2016.
    [abstract] [bibtex] [conf. version: pdf / doi]
  6. Streaming Symmetric Norms via Measure Concentration (AA, ME)
    Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang.
    In STOC 2017.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  7. Tight Bounds for Gomory-Hu-like Cut Counting (AA)
    Rajesh Chitnis, Lior Kamma, and Robert Krauthgamer.
    In Proceedings of WG 2016.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides]
  8. Sparsification of Two-Variable Valued CSPs (AA)
    Arnold Filtser and Robert Krauthgamer.
    SIAM Journal on Discrete Mathematics, 2017.
    [abstract] [bibtex] [full version: arXiv] [journal version: pdf / doi]
  9. Local Reconstruction of Low-Rank Matrices and Subspaces (AA)
    Roee David, Elazar Goldenberg, and Robert Krauthgamer.
    To appear in Random Structures and Algorithms, March 2017.
    [abstract] [full version: ECCC Report TR15-128 / doi]
  10. Towards Resistance Sparsifiers (AA)
    Michael Dinitz, Robert Krauthgamer, and Tal Wagner.
    In Proceedings of RANDOM 2015.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  11. Approximate Nearest Neighbor Search in Metrics of Planar Graphs (AA, ME)
    Ittai Abraham, Shiri Chechik, Robert Krauthgamer, and Udi Wieder.
    In Proceedings of APPROX 2015.
    [abstract] [bibtex] [conf. version: pdf / doi]
  12. Metric Decompositions of Path-Separable Graphs (AA, ME)
    Lior Kamma, and Robert Krauthgamer.
    Algorithmica, 2017.
    [abstract] [bibtex] [full version: arXiv / doi]
  13. Sketching and Embedding are Equivalent for Norms (AA, ME)
    To appear in SIAM Journal on Computing, 2017. Alexandr Andoni, Robert Krauthgamer and Ilya Razenshteyn.
    In Proceedings of STOC 2015.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides]
  14. Sketching Cuts in Graphs and Hypergraphs (AA)
    Dmitry Kogan and Robert Krauthgamer.
    In Proceedings of ITCS 2015.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  15. Cheeger-Type Approximation for Sparsest st-Cut (AA, ME)
    Robert Krauthgamer and Tal Wagner.
    ACM Transactions on Algorithms, 2016.
    [abstract] [bibtex] [journal version: pdf / doi / arXiv]
  16. Spectral Approaches to Nearest Neighbor Search (AA, ME)
    Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, and Robert Krauthgamer.
    In Proceedings of FOCS 2014.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides / video lecture]
  17. On Sketching Quadratic Forms (AA)
    Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang.
    In Proceedings of ITCS 2016.
    Merges arXiv:1403.7058 titled "The Sketching Complexity of Graph Cuts" with arXiv:1412.8225.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  18. Orienting Fully Dynamic Graphs with Worst-Case Time Bounds (AA)
    Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon.
    In Proceedings of ICALP 2014.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  19. Multiply Balanced k-Partitioning (AA)
    Amihood Amir, Jessica Ficler, Robert Krauthgamer, Liam Roditty, and Oren Sar Shalom.
    In Proceedings of LATIN 2014.
    [abstract] [bibtex] [conf. version: pdf / doi]
  20. Towards (1+ε)-Approximate Flow Sparsifiers (AA, ME)
    Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer.
    In Proceedings of SODA 2014.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides]
  21. Non-Uniform Graph Partitioning (AA)
    Robert Krauthgamer, Joseph (Seffi) Naor, Roy Schwartz, and Kunal Talwar.
    In Proceedings of SODA 2014.
    [abstract] [bibtex] [conf. version: pdf / doi]
  22. Do Semidefinite Relaxations Solve Sparse PCA up to the Information Limit? (AA)
    Robert Krauthgamer, Boaz Nadler, and Dan Vilenchik.
    Annals of Statistics, 2015.
    [abstract] [bibtex] [journal version: pdf / arXiv / doi]
  23. Cutting corners cheaply, or how to remove Steiner points (AA, ME)
    Lior Kamma, Robert Krauthgamer, and Huy L. Nguyen
    SIAM Journal on Computing, 2015. Preliminary version in Proceedings of SODA 2014.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [journal version: pdf / doi]
  24. Adaptive Metric Dimensionality Reduction (AA, ME)
    Lee-Ad Gottlieb, Aryeh Kontorovich and Robert Krauthgamer.
    Invited to a special issue of Theoretical Computer Science, 2016. In Proceedings of ALT 2013.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: arXiv / doi]
  25. Mimicking Networks and Succinct Representations of Terminal Cuts (AA)
    Robert Krauthgamer and Inbal Rika.
    In Proceedings of SODA 2013.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  26. Faster Clustering via Preprocessing (AA, ME)
    Tsvi Kopelowitz and Robert Krauthgamer.
    Manuscript, July 2012.
    [abstract] [full version: arXiv]
  27. Everywhere-Sparse Spanners via Dense Subgraphs (AA)
    Eden Chlamtac, Michael Dinitz, and Robert Krauthgamer.
    In Proceedings of FOCS 2012.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  28. Preserving Terminal Distances using Minors (AA, ME)
    Robert Krauthgamer, and Huy L. Nguyen, and Tamar Zondiner.
    SIAM Journal on Discrete Mathematics, 2014. Preliminary version (authored by Krauthgamer and Zondiner) in Proceedings of ICALP 2012.
    [
    abstract] [bibtex] [conf. version: pdf / doi / arXiv] [journal version: pdf / doi]
  29. The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme (AA, ME)
    Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer.
    SIAM Journal on Computing, 2016. Preliminary version in Proceedings of STOC 2012.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi / arXiv]
  30. Efficient Regression in Metric Spaces via Approximate Lipschitz Extension (AA, ME)
    Lee-Ad Gottlieb, Aryeh Kontorovich and Robert Krauthgamer.
    IEEE Transactions on Information Theory, 2017. Preliminary version in Proceedings of SIMBAD 2013.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [journal version: pdf / doi]
  31. Min-Max Graph Partitioning and Small-Set Expansion (AA, ME)
    Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, and Roy Schwartz.
    Invited to a special issue of SIAM Journal on Computing, 2014. Preliminary version in Proceedings of FOCS 2011.
    [abstract] [bibtex] [conf. version: pdf / doi / arXiv] [journal version: pdf / doi]
  32. Streaming Algorithms via Precision Sampling (AA, ME)
    Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak
    In Proceedings of FOCS 2011.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  33. Fault-Tolerant Spanners: Better and Simpler (AA, ME)
    Michael Dinitz, and Robert Krauthgamer
    In Proceedings of PODC 2011.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  34. Directed Spanners via Flow-Based Linear Programs (AA, ME)
    Michael Dinitz, and Robert Krauthgamer
    In Proceedings of STOC 2011.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  35. Approximating sparsest cut in graphs of bounded treewidth (AA)
    Eden Chlamtac, Robert Krauthgamer, and Prasad Raghavendra
    In Proceedings of APPROX 2010.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  36. Vertex Sparsifiers: New Results from Old Techniques (AA, ME)
    Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam-Cohen and Kunal Talwar.
    SIAM Journal on Computing, 2014. Preliminary version in Proceedings of APPROX 2010.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [journal version: pdf / doi] [slides] [video lecture]
  37. Proximity algorithms for nearly-doubling spaces (AA, ME)
    Lee-Ad Gottlieb, and Robert Krauthgamer.
    SIAM Journal on Discrete Mathematics, 2013. Preliminary version in Proceedings of APPROX 2010.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi]
  38. Efficient classification for metric data (AA, ME)
    Lee-Ad Gottlieb, Aryeh (Leonid) Kontorovich and Robert Krauthgamer.
    IEEE Transactions on Information Theory, 2014. Preliminary version in Proceedings of COLT 2010.
    [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv] [journal version: pdf / doi]
  39. Polylogarithmic approximation for edit distance and the asymmetric query complexity (AA)
    Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak
    In Proceedings of FOCS 2010.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  40. Partitioning Graphs into Balanced Components (AA, ME)
    Robert Krauthgamer, Joseph (Seffi) Naor, and Roy Schwartz.
    In Proceedings of SODA 2009.
    [abstract] [bibtex] [conf. version: pdf / doi]
  41. Approximate Line Nearest Neighbor in High Dimensions (AA, ME)
    Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen
    In Proceedings of SODA 2009.
    [abstract] [bibtex] [conf. version: pdf / doi]
  42. Overcoming the l_1 non-embeddability barrier: Algorithms for product metrics (AA, ME)
    Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
    In Proceedings of SODA 2009.
    [abstract] [bibtex] [conf. version: pdf / doi] [slides]
  43. The Smoothed Complexity of Edit Distance (AA)
    Alexandr Andoni and Robert Krauthgamer
    ACM Transactions on Algorithms, 2012. Preliminary version in Proceedings of ICALP 2008.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi]
  44. Distance Estimation Revisited: Drawing a Computational View of Embeddings (AA, CC, ME)
    Alexandr Andoni and Robert Krauthgamer
    Manuscript, July 2007.
  45. Metric Clustering via Consistent Labeling (AA, ME)
    Robert Krauthgamer and Tim Roughgarden
    Theory of Computing (ToC), 2011. Preliminary version in Proceedings of SODA 2008.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi]
  46. The Computational Hardness of Estimating Edit Distance (AA, CC, ME)
    Alexandr Andoni and Robert Krauthgamer
    Invited to a special issue of SIAM Journal on Computing, 2010. Preliminary version in Proceedings of FOCS 2007.
    [
    abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi] [slides]
  47. Earth Mover Distance over High-Dimensional Spaces (AA, ME)
    Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
    In Proceedings of SODA 2008. Previously as ECCC Report TR07-04, April 2007.
    [abstract] [bibtex] [report version: pdf] [conf. version: pdf / doi]
  48. Greedy list intersection (AA)
    Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, and Atri Rudra
    In Proceedings of ICDE 2008.
    [abstract] [bibtex] [conf. version: pdf / doi]
  49. Pricing commodities, or how to sell when buyers have restricted valuations (AA)
    Robert Krauthgamer, Aranyak Mehta, and Atri Rudra
    Invited to a special issue of Theoretical Computer Science, 2011. Preliminary version in Proceedings of WAOA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi]
  50. On triangulation of simple networks (AA, ME)
    Robert Krauthgamer
    In Proceedings of SPAA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi]
  51. Estimating the Sortedness of a Data Stream (AA, CC)
    Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of SODA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi]
  52. Algorithms on negatively curved spaces (AA, ME)
    Robert Krauthgamer and James R. Lee
    In Proceedings of FOCS 2006.
    [abstract] [bibtex] [conf. version: pdf / doi]
  53. Embedding the Ulam metric into l_1 (AA, ME)
    Moses Charikar and Robert Krauthgamer
    Theory of Computing (ToC), 2006.
    [abstract] [bibtex] [journal version: ps / pdf / doi]
  54. Improved lower bounds for embeddings into L_1 (AA, ME)
    Robert Krauthgamer and Yuval Rabani
    SIAM Journal on Computing, 2009. Preliminary version in Proceedings of SODA 2006.
    [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: pdf / doi]
  55. The sketching complexity of pattern matching (AA, CC)
    Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of RANDOM 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
  56. Approximating edit distance efficiently (AA, ME)
    Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of FOCS 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
  57. The black-box complexity of nearest neighbor search (AA, ME)
    Robert Krauthgamer and James R. Lee
    Invited to a special issue of Theoretical Computer Science, 2005. Preliminary version in Proceedings of ICALP 2004.
    [abstract] [bibtex] [conf. version] [journal version: ps / pdf / doi]
  58. Object location in realistic networks (AA, ME)
    Kirsten Hildrum, Robert Krauthgamer and John Kubiatowicz
    In Proceedings of SPAA 2004.
    [abstract] [bibtex] [conf. version: ps / pdf]
  59. Navigating nets: Simple algorithms for proximity search (AA, ME)
    Robert Krauthgamer and James R. Lee
    In Proceedings of SODA 2004.
    [abstract] [bibtex] [conf. version: ps / pdf] [slides]
  60. Approximate classification via earthmover metrics (AA, ME)
    Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Eva Tardos
    In Proceedings of SODA 2004.
    [abstract] [bibtex] [conf. version]
  61. Bounded geometries, fractals, and low-distortion embeddings (AA ,ME)
    Anupam Gupta, Robert Krauthgamer and James R. Lee
    In Proceedings of FOCS 2003.
    [abstract] [bibtex] [conf. version: ps / pdf]
  62. Detecting protein sequence conservation via metric embeddings (AA ,ME)
    Eran Halperin, Jeremy Buhler, Richard Karp, Robert Krauthgamer and Ben Westover
    In 11th Conference on Intelligent Systems for Molecular Biology (ISMB 2003), pp. 122-129, June 2003.
    [abstract] [conf. version: pdf / doi]
  63. Constant factor approximation of vertex-cuts in planar graphs (AA)
    Eyal Amir, Robert Krauthgamer and Satish Rao
    In Proceedings of STOC 2003.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
  64. Integrality ratio for Group Steiner Trees and Directed Steiner Trees (AA)
    Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan and Nan Wang
    SIAM Journal on Computing, 2007. Preliminary version in Proceedings of SODA'03.
    [abstract] [bibtex] [slides] [conf. version] [journal version: ps / pdf / doi]
  65. Property testing of data dimensionality (AA ,CC ,ME)
    Robert Krauthgamer and Ori Sasson
    In Proceedings of SODA 2003.
    [abstract] [bibtex] [slides] [conf. version: ps / pdf]
  66. The probable value of the Lovasz-Schrijver relaxations for maximum independent set (AA)
    Uriel Feige and Robert Krauthgamer
    SIAM Journal on Computing, 32(2):345-370, 2003. Previously as Weizmann Institute Technical Report # MCS-02-01, January 2002.
    [abstract] [bibtex] [report version] [journal version: ps / pdf] [my slides from the Bertinoro Workshop]
  67. Online server allocation in a server farm via benefit task systems (AA ,WWW)
    T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber and Maxim Sviridenko.
    In Proceedings of STOC 2001.
    [abstract] [bibtex] [conf. version: ps pdf] [slides: ppt pdf)]
  68. On approximating the achromatic number (AA ,CC)
    Guy Kortsarz and Robert Krauthgamer
    SIAM Journal on Discrete Mathematics, 2001. Preliminary version in Proceedings of SODA 2001.
    [abstract] [bibtex] [conf. version] [full version]
  69. A polylogarithmic approximation of the minimum bisection (AA)
    Uriel Feige and Robert Krauthgamer
    SIAM Journal on Computing, 2002. Preliminary version in Proceedings of FOCS '00.
    Awarded the SIAM Outstanding Paper Prize in July 2005.
    Invited to SIAM Review (SIGEST section), 2006.
    [abstract] [bibtex] [conf. version] [journal version] [further expanded version: ps / pdf / doi] [slides]
  70. Approximating the minimum bisection size (AA) [abstract]
    Uriel Feige, Robert Krauthgamer and Kobbi Nissim
    In 32nd Symposium on Theory of Computing (STOC '00), pp. 530-536, May 2000. [conf. version]
    A journal version for some results from this paper:
  71. Improved classification via connectivity information (AA ,WWW) [abstract]
    Andrei Broder, Robert Krauthgamer and Michael Mitzenmacher.
    In 11th Symposium of Discrete Algorithms (SODA '00), pp. 576-585, January 2000. [conf. version]
  72. Finding and certifying a large hidden clique in a semi-random graph (AA)
    Uriel Feige and Robert Krauthgamer
    Random Structures and Algorithms 16(2): 195-208, 2000. Previously as Weizmann Institute Technical Report # MCS99-04, January 1999.
    [abstract] [report version] [journal version] [my slides from the Bertinoro Workshop]
  73. Improved performance guarantees for bandwidth minimization heuristics (AA)
    Uriel Feige and Robert Krauthgamer
    Unpublished manuscript, November 1998. [manuscript]
  74. Networks on which hot-potato routing does not livelock (AA)
    Uriel Feige and Robert Krauthgamer
    Distributed Computing, 13(1):53-58 , 2000.
    [abstract] [bibtex] [journal version: ps / pdf / doi]
  75. Stereoscopic families of permutations, and their applications (AA ,ME) [abstract]
    Uriel Feige and Robert Krauthgamer
    In 5th Israel Symposium on the Theory of Computing and Systems (ISTCS '97), pp. 85-95, June 1997.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]

Computational Complexity

  1. Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern (AA, CC)
    Robert Krauthgamer and Ohad Trabelsi.
    Manuscript, August 2017.
    [abstract] [full version: arXiv]
  2. Conditional Lower Bounds for All-Pairs Max-Flow (AA, CC)
    Robert Krauthgamer and Ohad Trabelsi.
    In ICALP 2017.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  3. Local Reconstruction of Low-Rank Matrices and Subspaces (AA)
    Roee David, Elazar Goldenberg, and Robert Krauthgamer.
    To appear in Random Structures and Algorithms, March 2017.
    [abstract] [full version: ECCC Report TR15-128 / doi]
  4. How hard is it to approximate the best Nash equilibrium? (CC)
    Elad Hazan and Robert Krauthgamer
    SIAM Journal on Computing, 2011. Preliminary version in Proceedings of SODA 2009.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi]
  5. Distance Estimation Revisited: Drawing a Computational View of Embeddings (AA, CC, ME)
    Alexandr Andoni and Robert Krauthgamer
    Manuscript, July 2007.
  6. The Computational Hardness of Estimating Edit Distance (AA, CC, ME)
    Alexandr Andoni and Robert Krauthgamer
    Invited to a special issue of SIAM Journal on Computing, 2010. Preliminary version in Proceedings of FOCS 2007.
    [
    abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi] [slides]
  7. Earth Mover Distance over High-Dimensional Spaces (AA, ME)
    Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
    In Proceedings of SODA 2008. Previously as ECCC Report TR07-04, April 2007.
    [abstract] [bibtex] [report version: pdf] [conf. version: pdf / doi]
  8. Estimating the Sortedness of a Data Stream (AA, CC)
    Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of SODA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi]
  9. On the hardness of approximating multicut and sparsest-cut (CC)
    Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar
    Invited to special issue of Computational Complexity, 2006. Preliminary version in Proceedings of CCC 2005.
    [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: ps / pdf / doi]
  10. The sketching complexity of pattern matching (AA, CC)
    Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of RANDOM 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
  11. Asymmetric k-center is log^*n-hard to Approximate (CC)
    Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, and Joseph (Seffi) Naor
    Journal of the ACM, 2005. Preliminary version in ECCC Report TR03-035, May 2003.
    [abstract] [bibtex] [report version] [journal version: ps / pdf]
  12. Polylogarithmic inapproximability (CC)
    Eran Halperin and Robert Krauthgamer
    In Proceedings of STOC 2003.
    [abstract] [bibtex] [conf. version: ps / pdf]
  13. Property testing of data dimensionality (AA ,CC ,ME)
    Robert Krauthgamer and Ori Sasson
    In Proceedings of SODA 2003.
    [abstract] [bibtex] [slides] [conf. version: ps / pdf]
  14. Hardness of approximation for vertex-connectivity network design problems (CC)
    Guy Kortsarz, Robert Krauthgamer, and James R. Lee
    SIAM Journal on Computing, 2004. Preliminary version in Proceedings of APPROX 2002.
    [abstract] [bibtex] [conf. version] [journal version]
  15. Private approximation of NP-hard functions (CC)
    Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz and Kobbi Nissim
    In 33rd Symposium on Theory of Computing (STOC '01), pp. 550-559, July 2001.
    [abstract] [bibtex] [conf. version]
  16. On approximating the achromatic number (AA ,CC)
    Guy Kortsarz and Robert Krauthgamer
    SIAM Journal on Discrete Mathematics, 2001. Preliminary version in Proceedings of SODA 2001.
    [abstract] [bibtex] [conf. version] [full version]

Metric Spaces and Embeddings

  1. Refined Vertex Sparsifiers of Planar Graphs (AA, ME)
    Robert Krauthgamer and Inbal Rika.
    Manuscript, February 2017.
    [abstract] [full version: arXiv]
  2. Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order (AA, ME)
    Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, and Lin F. Yang.
    Manuscript, September 2016 (revised November 2017).
    [abstract] [full version: arXiv]
  3. Color-Distance Oracles and Snippets (AA, ME)
    Tsvi Kopelowitz, and Robert Krauthgamer.
    In Proceedings of CPM 2016.
    [abstract] [bibtex] [conf. version: pdf / doi]
  4. Streaming Symmetric Norms via Measure Concentration (AA, ME)
    Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang.
    In STOC 2017.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  5. Approximate Nearest Neighbor Search in Metrics of Planar Graphs (AA, ME)
    Ittai Abraham, Shiri Chechik, Robert Krauthgamer, and Udi Wieder.
    In Proceedings of APPROX 2015.
    [abstract] [bibtex] [conf. version: pdf / doi]
  6. Metric Decompositions of Path-Separable Graphs (AA, ME)
    Lior Kamma, and Robert Krauthgamer.
    Algorithmica, 2017.
    [abstract] [bibtex] [full version: arXiv / doi]
  7. Sketching and Embedding are Equivalent for Norms (AA, ME)
    To appear in SIAM Journal on Computing, 2017. Alexandr Andoni, Robert Krauthgamer and Ilya Razenshteyn.
    In Proceedings of STOC 2015.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides]
  8. Cheeger-Type Approximation for Sparsest st-Cut (AA, ME)
    Robert Krauthgamer and Tal Wagner.
    ACM Transactions on Algorithms, 2016.
    [abstract] [bibtex] [journal version: pdf / doi / arXiv]
  9. Spectral Approaches to Nearest Neighbor Search (AA, ME)
    Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, and Robert Krauthgamer.
    In Proceedings of FOCS 2014.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides / video lecture]
  10. Towards (1+ε)-Approximate Flow Sparsifiers (AA, ME)
    Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer.
    In Proceedings of SODA 2014.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides]
  11. Cutting corners cheaply, or how to remove Steiner points (AA, ME)
    Lior Kamma, Robert Krauthgamer, and Huy L. Nguyen
    SIAM Journal on Computing, 2015. Preliminary version in Proceedings of SODA 2014.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [journal version: pdf / doi]
  12. Adaptive Metric Dimensionality Reduction (AA, ME)
    Lee-Ad Gottlieb, Aryeh Kontorovich and Robert Krauthgamer.
    Invited to a special issue of Theoretical Computer Science, 2016. In Proceedings of ALT 2013.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: arXiv / doi]
  13. Faster Clustering via Preprocessing (AA, ME)
    Tsvi Kopelowitz and Robert Krauthgamer.
    Manuscript, July 2012.
    [abstract] [full version: arXiv]
  14. Preserving Terminal Distances using Minors (AA, ME)
    Robert Krauthgamer, and Huy L. Nguyen, and Tamar Zondiner.
    SIAM Journal on Discrete Mathematics, 2014. Preliminary version (authored by Krauthgamer and Zondiner) in Proceedings of ICALP 2012.
    [
    abstract] [bibtex] [conf. version: pdf / doi / arXiv] [journal version: pdf / doi]
  15. The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme (AA, ME)
    Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer.
    SIAM Journal on Computing, 2016. Preliminary version in Proceedings of STOC 2012.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi / arXiv]
  16. Efficient Regression in Metric Spaces via Approximate Lipschitz Extension (AA, ME)
    Lee-Ad Gottlieb, Aryeh Kontorovich and Robert Krauthgamer.
    IEEE Transactions on Information Theory, 2017. Preliminary version in Proceedings of SIMBAD 2013.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [journal version: pdf / doi]
  17. Min-Max Graph Partitioning and Small-Set Expansion (AA, ME)
    Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, and Roy Schwartz.
    Invited to a special issue of SIAM Journal on Computing, 2014. Preliminary version in Proceedings of FOCS 2011.
    [abstract] [bibtex] [conf. version: pdf / doi / arXiv] [journal version: pdf / doi]
  18. Streaming Algorithms via Precision Sampling (AA, ME)
    Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak
    In Proceedings of FOCS 2011.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  19. Fault-Tolerant Spanners: Better and Simpler (AA, ME)
    Michael Dinitz, and Robert Krauthgamer
    In Proceedings of PODC 2011.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  20. Directed Spanners via Flow-Based Linear Programs (AA, ME)
    Michael Dinitz, and Robert Krauthgamer
    In Proceedings of STOC 2011.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
  21. Vertex Sparsifiers: New Results from Old Techniques (AA, ME)
    Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam-Cohen and Kunal Talwar.
    SIAM Journal on Computing, 2014. Preliminary version in Proceedings of APPROX 2010.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [journal version: pdf / doi] [slides] [video lecture]
  22. Proximity algorithms for nearly-doubling spaces (AA, ME)
    Lee-Ad Gottlieb, and Robert Krauthgamer.
    SIAM Journal on Discrete Mathematics, 2013. Preliminary version in Proceedings of APPROX 2010.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi]
  23. Efficient classification for metric data (AA, ME)
    Lee-Ad Gottlieb, Aryeh (Leonid) Kontorovich and Robert Krauthgamer.
    IEEE Transactions on Information Theory, 2014. Preliminary version in Proceedings of COLT 2010.
    [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv] [journal version: pdf / doi]
  24. A nonlinear approach to dimension reduction (ME)
    Lee-Ad Gottlieb and Robert Krauthgamer
    Discrete and Computational Geometry, 2015. Preliminary version in Proceedings of SODA 2011.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: arXiv / doi] [presentation: slides / video lecture]
  25. Partitioning Graphs into Balanced Components (AA, ME)
    Robert Krauthgamer, Joseph (Seffi) Naor, and Roy Schwartz.
    In Proceedings of SODA 2009.
    [abstract] [bibtex] [conf. version: pdf / doi]
  26. Approximate Line Nearest Neighbor in High Dimensions (AA, ME)
    Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen
    In Proceedings of SODA 2009.
    [abstract] [bibtex] [conf. version: pdf / doi]
  27. Overcoming the l_1 non-embeddability barrier: Algorithms for product metrics (AA, ME)
    Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
    In Proceedings of SODA 2009.
    [abstract] [bibtex] [conf. version: pdf / doi] [slides]
  28. Distance Estimation Revisited: Drawing a Computational View of Embeddings (AA, CC, ME)
    Alexandr Andoni and Robert Krauthgamer
    Manuscript, July 2007.
  29. Metric Clustering via Consistent Labeling (AA, ME)
    Robert Krauthgamer and Tim Roughgarden
    Theory of Computing (ToC), 2011. Preliminary version in Proceedings of SODA 2008.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi]
  30. The Computational Hardness of Estimating Edit Distance (AA, CC, ME)
    Alexandr Andoni and Robert Krauthgamer
    Invited to a special issue of SIAM Journal on Computing, 2010. Preliminary version in Proceedings of FOCS 2007.
    [
    abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi] [slides]
  31. Earth Mover Distance over High-Dimensional Spaces (AA, ME)
    Alexandr Andoni, Piotr Indyk and Robert Krauthgamer
    In Proceedings of SODA 2008. Previously as ECCC Report TR07-04, April 2007.
    [abstract] [bibtex] [report version: pdf] [conf. version: pdf / doi]
  32. On triangulation of simple networks (AA, ME)
    Robert Krauthgamer
    In Proceedings of SPAA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi]
  33. Algorithms on negatively curved spaces (AA, ME)
    Robert Krauthgamer and James R. Lee
    In Proceedings of FOCS 2006.
    [abstract] [bibtex] [conf. version: pdf / doi]
  34. Embedding the Ulam metric into l_1 (AA, ME)
    Moses Charikar and Robert Krauthgamer
    Theory of Computing (ToC), 2006.
    [abstract] [bibtex] [journal version: ps / pdf / doi]
  35. Improved lower bounds for embeddings into L_1 (AA, ME)
    Robert Krauthgamer and Yuval Rabani
    SIAM Journal on Computing, 2009. Preliminary version in Proceedings of SODA 2006.
    [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: pdf / doi]
  36. Approximating edit distance efficiently (AA, ME)
    Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar
    In Proceedings of FOCS 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]
  37. Measured descent: A new embedding method for finite metrics (ME)
    Robert Krauthgamer, James R. Lee, Manor Mendel and Assaf Naor
    Geometric and Functional Analysis (GAFA), 2005. Preliminary version in Proceedings of FOCS 2004.
    [abstract] [bibtex] [conf. version: ps / pdf / doi] [journal version: ps / pdf / doi / arXiv]
  38. The black-box complexity of nearest neighbor search (AA, ME)
    Robert Krauthgamer and James R. Lee
    Invited to a special issue of Theoretical Computer Science, 2005. Preliminary version in Proceedings of ICALP 2004.
    [abstract] [bibtex] [conf. version] [journal version: ps / pdf / doi]
  39. Object location in realistic networks (AA, ME)
    Kirsten Hildrum, Robert Krauthgamer and John Kubiatowicz
    In Proceedings of SPAA 2004.
    [abstract] [bibtex] [conf. version: ps / pdf]
  40. Navigating nets: Simple algorithms for proximity search (AA, ME)
    Robert Krauthgamer and James R. Lee
    In Proceedings of SODA 2004.
    [abstract] [bibtex] [conf. version: ps / pdf] [slides]
  41. Approximate classification via earthmover metrics (AA, ME)
    Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Eva Tardos
    In Proceedings of SODA 2004.
    [abstract] [bibtex] [conf. version]
  42. Bounded geometries, fractals, and low-distortion embeddings (AA ,ME)
    Anupam Gupta, Robert Krauthgamer and James R. Lee
    In Proceedings of FOCS 2003.
    [abstract] [bibtex] [conf. version: ps / pdf]
  43. Detecting protein sequence conservation via metric embeddings (AA ,ME)
    Eran Halperin, Jeremy Buhler, Richard Karp, Robert Krauthgamer and Ben Westover
    In 11th Conference on Intelligent Systems for Molecular Biology (ISMB 2003), pp. 122-129, June 2003.
    [abstract] [conf. version: pdf / doi]
  44. The intrinsic dimensionality of graphs (ME)
    Robert Krauthgamer and James R. Lee
    Combinatorica, 2007. Preliminary version in Proceedings of STOC 2003.
    [abstract] [bibtex] [conf. version: ps / pdf] [journal version: ps / pdf / doi] [slides: ppt / pdf]
  45. Property testing of data dimensionality (AA ,CC ,ME)
    Robert Krauthgamer and Ori Sasson
    In Proceedings of SODA 2003.
    [abstract] [bibtex] [slides] [conf. version: ps / pdf]
  46. Metric embeddings -- beyond one-dimensional distortion (ME)
    Robert Krauthgamer, Nati Linial and Avner Magen
    In Discrete and Computational Geometry, 2004. (Earlier version in UC Berkeley Technical Report #CSD-02-1181, May 2002.)
    [abstract] [bibtex] [report version] [journal version]
  47. Stereoscopic families of permutations, and their applications (AA ,ME) [abstract]
    Uriel Feige and Robert Krauthgamer
    In 5th Israel Symposium on the Theory of Computing and Systems (ISTCS '97), pp. 85-95, June 1997.
    [abstract] [bibtex] [conf. version: ps / pdf / doi]

Web-related

  1. Focused Sampling: Computing Topical Web Statistics (WWW)
    Ziv Bar-Yossef, Robert Krauthgamer, and Tapas Kanungo
    IBM Research Report RJ 10339, February 2005.
    [abstract] [bibtex] [report version]
  2. Online server allocation in a server farm via benefit task systems (AA ,WWW)
    T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber and Maxim Sviridenko.
    In Proceedings of STOC 2001.
    [abstract] [bibtex] [conf. version: ps pdf] [slides: ppt pdf)]
  3. Improved classification via connectivity information (AA ,WWW) [abstract]
    Andrei Broder, Robert Krauthgamer and Michael Mitzenmacher.
    In 11th Symposium of Discrete Algorithms (SODA '00), pp. 576-585, January 2000. [conf. version]