Online Publications of Robert Krauthgamer

• Please read the copyright notice.
• I annotated papers with the following (partial) keywords:
  • AA = Analysis of Algorithms
  • CC = Computational Complexity
  • ME = Metric Spaces and Embeddings
  • WWW = Web-related
• See also the papers' abstracts and the papers by keyword.
• Note: Some papers/slides are gzipped postcript/powerpoint files.

Papers

1. Moderate Dimension Reduction for k-Center Clustering (AA, ME)
   Shaofeng H.-C. Jiang, Robert Krauthgamer, and Shay Sapir.
   In Proceedings of SoCG 2024.
   [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
2. Fully Scalable MPC Algorithms for Clustering in High Dimension (AA, ME)
   Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Vesely.
   In Proceedings of ICALP 2024.
   [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides / video lecture]
3. Cut Sparsification and Succinct Representation of Submodular Hypergraphs (AA)
   Yotam Kenneth and Robert Krauthgamer.
   In Proceedings of ICALP 2024.
   [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
4. Lower Bounds for Pseudo-Deterministic Counting in a Stream (AA, CC)
   Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, and Shay Sapir.
   In Proceedings of ICALP 2023.
   [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
5. Streaming Euclidean Max-Cut: Dimension vs Data Reduction (AA, ME)
   Xiaoyu Chen, Shaofeng H.-C. Jiang, and Robert Krauthgamer.
   In Proceedings of STOC 2023.
   [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
6. Clustering Permutations: New Techniques with Streaming Applications (AA, ME)
   Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer.
   In Proceedings of ITCS 2023.
   [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
7. An Algorithmic Bridge Between Hamming and Levenshtein Distances (AA)
   Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha.
   In Proceedings of ITCS 2023.
   [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
8. Recovery Guarantees for Distributed-OMP (AA)
   Chen Amiraz, Robert Krauthgamer, and Boaz Nadler.
   In Proceedings of AISTATS 2024.
   [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv]
9. Exact Flow Sparsification Requires Unbounded Size (AA)
   Robert Krauthgamer and Ron Mosenzon.
   In Proceedings of SODA 2023.
   [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
10. Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs (AA)
    Itai Boneh and Robert Krauthgamer.
    Manuscript, April 2022.
    [abstract] [full version: arXiv]
11. The Power of Uniform Sampling for Coresets (AA, ME)
    Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu.
    In Proceedings of FOCS 2022.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
12. Streaming Facility Location in High Dimension via Geometric Hashing (AA, ME)
    The latest version (on arxiv) with improved bounds has an additional coauthor (Arnold Filtser).
    Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Vesely, and Mingwei Yang.
    In Proceedings of FOCS 2022.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
13. Comparison of Matrix Norm Sparsification (AA)
    Robert Krauthgamer and Shay Sapir.
    Algorithmica, 2023.
    [abstract] [bibtex] [journal version: arXiv / doi]
14. Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time (AA)
    Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi.
    In Proceedings of FOCS 2022.
    An early version of this paper was titled "Gomory-Hu Tree in Subcubic Time".
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
15. Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal (AA)
    Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha.
    In Proceedings of FOCS 2022.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
16. Almost-Linear ε-Emulators for Planar Graphs (AA, ME)
    Hsien-Chih Chang, Robert Krauthgamer, and Zihan Tan.
    In Proceedings of STOC 2022.
    The full version has an improved bound and thus its title changed from almost-linear to near-linear.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version (improved bound): arXiv]
17. Friendly Cut Sparsifiers and Faster Gomory-Hu Trees (AA)
    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.
    In Proceedings of SODA 2022.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
18. Coresets for Kernel Clustering (AA, ME)
    Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, and Yubo Zhang.
    In Machine Learning, 2024.
    [abstract] [bibtex] [journal version: arXiv / doi]
19. Approximate Trace Reconstruction via Median String (in Average-Case) (AA, ME)
    Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer.
    In Proceedings of FSTTCS 2021.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
20. Coresets for Clustering with Missing Values (AA, ME)
    Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu.
    In Proceedings of NeurIPS 2021.
    [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv]
21. APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time (AA)
    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.
    In Proceedings of FOCS 2021.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
22. Spectral Hypergraph Sparsifiers of Nearly Linear Size (AA)
    Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida.
    In Proceedings of FOCS 2021.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
23. Smoothness of Schatten Norms and Sliding-Window Matrix Streams (AA)
    Robert Krauthgamer and Shay Sapir.
    To appear in Information Processing Letters, September 2023.
    [abstract] [bibtex] [journal version: arXiv / doi]
24. Distributed Sparse Normal Means Estimation with Sublinear Communication (AA)
    Chen Amiraz, Robert Krauthgamer, and Boaz Nadler.
    Information and Inference: A Journal of the IMA, 2022.
    [abstract] [bibtex] [journal version: arXiv / doi]
25. Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs (AA)
    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.
    In Proceedings of STOC 2021.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
26. Towards Tight Bounds for Spectral Sparsification of Hypergraphs (AA)
    Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida.
    In Proceedings of STOC 2021.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
27. Streaming Algorithms for Geometric Steiner Forest (AA, ME)
    Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Vesely.
    ACM Transactions on Algorithms, 2024. Preliminary version in Proceedings of ICALP 2022.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: arXiv / doi]
28. Near-Optimal Entrywise Sampling of Numerically Sparse Matrices (AA)
    Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, and Shay Sapir.
    In Proceedings of COLT 2021.
    [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv]
29. Approximating the Median under the Ulam Metric (AA, ME)
    Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer.
    In Proceedings of SODA 2021.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
30. Cut-Equivalent Trees are Optimal for Min-Cut Queries (AA)
    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.
    In Proceedings of FOCS 2020.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
31. Coresets for Clustering in Excluded-Minor Graphs and Beyond (AA, ME)
    Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu.
    In Proceedings of SODA 2021.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides / video lecture]
32. Faster Algorithms for Orienteering and k-TSP (AA, ME)
    Lee-Ad Gottlieb, Robert Krauthgamer, and Havana Rika.
    Theoretical Computer Science, 2022.
    [abstract] [bibtex] [journal version: arXiv / doi]
33. Sublinear Algorithms for Gap Edit Distance (AA)
    Elazar Goldenberg, Robert Krauthgamer, and Barna Saha.
    In Proceedings of FOCS 2019.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
34. Labelings vs. Embeddings: On Distributed Representations of Distances (AA, ME)
    Arnold Filtser, Lee-Ad Gottlieb, and Robert Krauthgamer.
    Discrete and Computational Geometry, 2023. Preliminary version in Proceedings of SODA 2020.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: arXiv / doi]
35. Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension (AA)
    Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, and Roi Sinoff.
    In Proceedings of ICML 2020.
    [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv]
36. Coresets for Clustering in Graphs of Bounded Treewidth (AA, ME)
    Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu.
    In Proceedings of ICML 2020.
    [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv]
37. Tight Recovery Guarantees for Orthogonal Matching Pursuit Under Gaussian Noise (AA)
    Chen Amiraz, Robert Krauthgamer, and Boaz Nadler.
    Information and Inference: A Journal of the IMA, 2020.
    [abstract] [bibtex] [journal version: arXiv / doi]
38. Almost-Smooth Histograms and Sliding-Window Graph Algorithms (AA)
    Robert Krauthgamer and David Reitblat.
    Algorithmica, 2022.
    [abstract] [bibtex] [full version: arXiv / doi]
39. Coresets for Ordered Weighted Clustering (AA, ME)
    Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu.
    In Proceedings of ICML 2019.
    [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv]
40. New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs (AA)
    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.
    Theory of Computing (ToC), 2021. Preliminary version in Proceedings of SODA 2020.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [journal version: pdf / doi]
41. Universal Streaming of Subset Norms (AA)
    Vladimir Braverman, Robert Krauthgamer, and Lin F. Yang.
    Theory of Computing (ToC), 2022.
    [abstract] [bibtex] [full version: arXiv] [journal version: pdf / doi]
42. On Solving Linear Systems in Sublinear Time (AA)
    Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow.
    In Proceedings of ITCS 2019.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides]
43. Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems (AA, ME)
    Arnold Filtser, Robert Krauthgamer, and Ohad Trabelsi.
    In Proceedings of SOSA 2019.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
44. Flow-Cut Gaps and Face Covers in Planar Graphs (AA, ME)
    Robert Krauthgamer, James R. Lee, and Havana (Inbal) Rika.
    In Proceedings of SODA 2019.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
45. Batch Sparse Recovery, or How to Leverage the Average Sparsity (AA)
    Alexandr Andoni, Lior Kamma, Robert Krauthgamer, and Eric Price.
    Manuscript, July 2018.
    [abstract] [full version: arXiv]
    
46. Faster Algorithms for All-Pairs Bounded Min-Cuts (AA, CC)
    Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf.
    In Proceedings of ICALP 2019.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
    
47. Stochastic Selection Problems with Testing (AA)
    Chen Attias, Robert Krauthgamer, Retsef Levi and Yaron Shaposhnik.
    Manuscript, December 2017.
    [abstract] [full version: SSRN]
    
48. The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern (AA, CC)
    Robert Krauthgamer and Ohad Trabelsi.
    In Proceedings of STACS 2019.
    Merges "Revisiting the Set Cover Conjecture" arXiv:1711.08041v1 and "Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern" arXiv:1708.07591.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv]
    
49. Refined Vertex Sparsifiers of Planar Graphs (AA, ME)
    Robert Krauthgamer and Havana (Inbal) Rika.
    SIAM Journal on Discrete Mathematics, 2020.
    [abstract] [bibtex] [full version: arXiv] [journal version: pdf / doi]
    
50. Conditional Lower Bounds for All-Pairs Max-Flow (AA, CC)
    Robert Krauthgamer and Ohad Trabelsi.
    ACM Transactions on Algorithms, 2018. Preliminary version in Proceedings of ICALP 2017.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: pdf / doi / arXiv]
    
51. Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order (AA)
    Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, and Lin F. Yang.
    In Proceedings of ICML 2018.
    [abstract] [bibtex] [conf. version: pdf / ee] [full version: arXiv]
52. Color-Distance Oracles and Snippets (AA, ME)
    Tsvi Kopelowitz, and Robert Krauthgamer.
    In Proceedings of CPM 2016.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
53. Streaming Symmetric Norms via Measure Concentration (AA, ME)
    Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang.
    In Proceedings of STOC 2017.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides]
    
54. Tight Bounds for Gomory-Hu-like Cut Counting (AA)
    Rajesh Chitnis, Lior Kamma, and Robert Krauthgamer.
    In Proceedings of WG 2016.
    Update: The latest version (on arXiv) contains additional references to previous work (which have some overlap with our results).
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [slides]
    
55. 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]
    
56. Local Reconstruction of Low-Rank Matrices and Subspaces (AA)
    Roee David, Elazar Goldenberg, and Robert Krauthgamer.
    Random Structures and Algorithms, 2017.
    [abstract] [bibtex] [full version: ECCC Report TR15-128 / doi]
    
57. 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]
    
58. 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]
    
59. Metric Decompositions of Path-Separable Graphs (AA, ME)
    Lior Kamma and Robert Krauthgamer.
    Algorithmica, 2017.
    [abstract] [bibtex] [full version: arXiv / doi]
    
60. Sketching and Embedding are Equivalent for Norms (AA, ME)
    Alexandr Andoni, Robert Krauthgamer and Ilya Razenshteyn.
    SIAM Journal on Computing, 2018. Preliminary version in Proceedings of STOC 2015.
    [abstract] [bibtex] [conf. version: pdf / doi] [full version: arXiv] [journal version: pdf / doi] [slides]
    
61. 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]
    
62. 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]
    
63. 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]
    
64. 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]
    
65. 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]
    
66. 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]
    
67. 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]
    
68. 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]
    
69. 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]
    
70. 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]
    
71. Adaptive Metric Dimensionality Reduction (AA, ME)
    Lee-Ad Gottlieb, Aryeh Kontorovich and Robert Krauthgamer.
    Invited to a special issue of Theoretical Computer Science, 2016. Preliminary version in Proceedings of ALT 2013.
    [abstract] [bibtex] [conf. version: pdf / doi] [journal version: arXiv / doi]
    
72. 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]
    
73. Faster Clustering via Preprocessing (AA, ME)
    Tsvi Kopelowitz and Robert Krauthgamer.
    Manuscript, July 2012.
    [abstract] [full version: arXiv]
    
74. 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]
    
75. 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]
    
76. 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]
    
77. 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]
    
78. 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]
    
79. 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]
    
80. 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]
    
81. 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]
    
82. 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]
    
83. 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]
    
84. 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]
    
85. 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]
    
86. 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]
    
87. 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]
    
88. 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]
    
89. 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]
    
90. 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]
    
91. 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]
    
92. 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]
    
93. Distance Estimation Revisited: Drawing a Computational View of Embeddings (AA, CC, ME)
    Alexandr Andoni and Robert Krauthgamer
    Manuscript, July 2007.
    
94. 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]
    
95. 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]
    
96. 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]
    
97. Greedy list intersection (AA)
    Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, and Atri Rudra
    In Proceedings of ICDE 2008.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
98. 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]
    
99. On triangulation of simple networks (AA, ME)
    Robert Krauthgamer
    In Proceedings of SPAA 2007.
    [abstract] [bibtex] [conf. version: pdf / doi]
    
100. 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 / ee]
     
101. Algorithms on negatively curved spaces (AA, ME)
     Robert Krauthgamer and James R. Lee
     In Proceedings of FOCS 2006.
     [abstract] [bibtex] [conf. version: pdf / doi]
     
102. 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]
     
103. 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 / ee] [journal version: pdf / doi]
     
104. 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]
     
105. 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]
     
106. 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]
     
107. 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]
     
108. 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]
     
109. 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]
     
110. 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]
     
111. 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]
112. 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]
     
113. 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]
114. 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]
115. 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]
     
116. 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]
117. 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]
118. Polylogarithmic inapproximability (CC)
     Eran Halperin and Robert Krauthgamer
     In Proceedings of STOC 2003.
     [abstract] [bibtex] [conf. version: ps / pdf]
119. 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 2003.
     [abstract] [bibtex] [slides] [conf. version] [journal version: ps / pdf / doi]
     
120. 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]
     
121. 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]
     
122. 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: ps / doi]
     
123. 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]
     
124. Private approximation of NP-hard functions (CC)
     Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz and Kobbi Nissim
     In 33rd Symposium on Theory of Computing (STOC 2001), pp. 550-559, July 2001.
     [abstract] [bibtex] [conf. version]
125. 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)]
     
126. 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]
     
127. A polylogarithmic approximation of the minimum bisection (AA)
     Uriel Feige and Robert Krauthgamer
     SIAM Journal on Computing, 2002. Preliminary version in Proceedings of FOCS 2000.
     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]
128. Approximating the minimum bisection size (AA) [abstract]
     Uriel Feige, Robert Krauthgamer and Kobbi Nissim
     In 32nd Symposium on Theory of Computing (STOC 2000), pp. 530-536, May 2000. [conf. version]
     A journal version for some results from this paper:
     • On cutting a few vertices from a graph
       Discrete Applied Mathematics, 127(3): 643-649, 2003.
       [abstract] [bibtex] [journal version: ps / pdf / doi]
129. Improved classification via connectivity information (AA ,WWW) [abstract]
     Andrei Broder, Robert Krauthgamer and Michael Mitzenmacher.
     In 11th Symposium of Discrete Algorithms (SODA 2000), pp. 576-585, January 2000. [conf. version]
     
130. 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]
     
131. Improved performance guarantees for bandwidth minimization heuristics (AA)
     Uriel Feige and Robert Krauthgamer
     Unpublished manuscript, November 1998. [manuscript]
     
132. 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]
     
133. 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 1997), pp. 85-95, June 1997.
     [abstract] [bibtex] [conf. version: ps / pdf / doi]
     

Additional Slides and Talks

• Data vs Dimension Reduction in High-Dimensional Streams [newer shorter slides, slides]
  Presented at Shonan workshop on New Frontiers in Locality in Computation, 2023.
  Earlier version at EPFL's Sublinear Algorithms workshop, December 2022.
  Earlier version at FOCS 2022 workshop on Advances on Metric Embeddings, November 2022.
• Sketching Graphs and Combinatorial Approximation
  Invited talk at SODA 2021. [slides]
  Earlier versions: Invited talk at ICALP 2020 [slides / video lecture], Invited talk at FSTTCS 2019.
• Vertex Sparsification of Cuts, Flows, and Distances [slides]
  Presented at WorKer (workshop on kernelization) in Norway, 2015.
• On Sketching Quadratic Forms [slides]
  Presented at the second Sublinear Day at MIT, 2015.
• Efficient Approximation of Edit Distance [slides]
  Invited talk at SPIRE 2013.
• Algorithmic Frontiers of Doubling Metric Spaces [slides] [video lecture]
  Presented at EPFL's Algorithmic Frontiers Workshop, 2012.
• Efficient Algorithms via Precision Sampling [slides / video lecture]
  Presented at the Open University's Fifth Israel CS Theory Day, 2012.
• Vertex Sparsifiers: New Results from Old Techniques [slides / video lecture]
  Presented at a Newton Insitute Embedding workshop, 2011.
• A metric notion of dimension and its applications to learning [slides / video lecture]
  Presented at ICML/COLT Workshop Learning in Non-(geo)metric Spaces, 2010.
• Overcoming the L_1 Non-Embeddability Barrier [slides]
  Presented at an IPAM workshop Quantitative and Computational Aspects of Metric Geometry, 2009.
• Similarity searching, or how to find your neighbors efficiently [slides: ppt / pdf]
  Presented at the Weizmann CS Research Day for Prospective Students and at the Weizmann FUN seminar, 2009.
• Metric Embeddings As Computational Primitives [slides] [video lecture: hi-res or lo-res] ]
  Presented at Princeton Workshop Geometry and Algorithms, 2008.
• On Embedding Edit Distance into L1 [slides]
  Presented at Dagstuhl workshop Probabilistic Methods in the Design and Analysis of Algorithms, 2007.

Theses

• Coping with NP-hardness: Approximating minimum bisection and heuristics for maximum clique [abstract]
  Robert Krauthgamer. Supervisor: Uriel Feige.
  Ph.D. thesis, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel. April 2001.
  [thesis: gzipped ps / pdf]
  
• Simple algorithms for hot-potato routing [abstract]
  Robert Krauthgamer. Supervisor: Uriel Feige.
  M.Sc. thesis, Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel. October 1996.
  [thesis: gzipped ps / pdf]
  

Non-Technical Papers

• 3rd Highlights of Algorithms (HALG 2018)
  In SIGACT news, September 2018.
  [pdf / doi]

Patents

Patents Issued

1. Dynamic resource allocation using known future benefits
   T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Maria Minkoff, Baruch Schieber and Maxim Sviridenko.
   US Patent 7085837, issued August 1, 2006, and 7765301, issued July 27, 2010.
2. Dynamic resource allocation using projected future benefits
   T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber and Maxim Sviridenko.
   US Patent 7308415, issued December 11, 2007.
3. Computer system management and throughput maximization under peak power constraints
   Nimrod Megiddo and Robert Krauthgamer.
   US Patent 7587621, issued September 8, 2009, and 8046605, issue October 25, 2011.
4. System, method, and service for using a focused random walk to produce samples on a topic from a collection of hyper-linked pages
   Ziv Bar-Yossef, Tapas Kanungo and Robert Krauthgamer.
   US Patent 7640488, issued December 29, 2009.
5. Method of obtaining data samples from a data stream and of estimating the sortedness of the data stream based on the samples
   Parikshit Gopalan, T. S. Jayram, and Robert Krauthgamer.
   US Patent 7797326, issued September 14, 2010.
6. Adaptive greedy method for ordering intersecting of a group of lists into a left-deep AND-tree
   Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman and Atri Rudra.
   US Patent 7925604, issued April 12, 2011.

   Patents Pending

7. System and method for detecting matches of small edit distance
   Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer and Ravi Kumar.
   IBM Invention Disclosure ARC-920050044-US1, filed September 2005.
8. Method, computer program product, and device for conducting a multi-criteria similarity search
   Tapas Kanungo Robert Krauthgamer, and James Rhodes.
   IBM Invention Disclosure ARC-920060059-US1, filed in US December 2006.