Robert Krauthgamer
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
97
Venues
19
Active years
2000–2026
Best venue rank
A*
Where they publish
Papers
97 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2026 | ESA | Fast Metric Decompositions in High Dimension. | Robert Krauthgamer, Asaf Petruschka, Nir Petruschka |
| 2026 | ICALP | The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends. | Lotte Blank, Sergio Cabello, Mohammad Taghi Hajiaghayi, Robert Krauthgamer, Sepideh Mahabadi, Andr Nusser, Jeff M. Phillips, Jonas Sauer |
| 2026 | SODA | All-Pairs Minimum Cut using (n | Yotam Kenneth-Mordoch, Robert Krauthgamer |
| 2026 | STOC | Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow. | Yotam Kenneth-Mordoch, Robert Krauthgamer |
| 2025 | ESA | Cut-Query Algorithms with Few Rounds. | Yotam Kenneth-Mordoch, Robert Krauthgamer |
| 2025 | FOCS | The Power of Recursive Embeddings for ℓp Metrics. | Robert Krauthgamer, Nir Petruschka, Shay Sapir |
| 2025 | STOC | Near-Optimal Dimension Reduction for Facility Location. | Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Di Yue |
| 2024 | AISTATS | Recovery Guarantees for Distributed-OMP. | Chen Amiraz, Robert Krauthgamer, Boaz Nadler |
| 2024 | ICALP | Fully-Scalable MPC Algorithms for Clustering in High Dimension. | Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Vesel |
| 2024 | ICALP | Cut Sparsification and Succinct Representation of Submodular Hypergraphs. | Yotam Kenneth, Robert Krauthgamer |
| 2023 | ICALP | Lower Bounds for Pseudo-Deterministic Counting in a Stream. | Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir |
| 2023 | SODA | Exact Flow Sparsification Requires Unbounded Size. | Robert Krauthgamer, Ron Mosenzon |
| 2023 | STOC | Streaming Euclidean Max-Cut: Dimension vs Data Reduction. | Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer |
| 2022 | FOCS | Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. | Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi |
| 2022 | FOCS | The Power of Uniform Sampling for Coresets. | Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu |
| 2022 | FOCS | Streaming Facility Location in High Dimension via Geometric Hashing. | Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Vesel, Mingwei Yang |
| 2022 | FOCS | Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. | Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha |
| 2022 | ICALP | Streaming Algorithms for Geometric Steiner Forest. | Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Vesel |
| 2022 | SODA | Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. | Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2022 | STOC | Almost-linear | Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan |
| 2021 | COLT | Near-Optimal Entrywise Sampling of Numerically Sparse Matrices. | Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir |
| 2021 | FOCS | APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. | Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2021 | FOCS | Spectral Hypergraph Sparsifiers of Nearly Linear Size. | Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
| 2021 | SODA | Coresets for Clustering in Excluded-minor Graphs and Beyond. | Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu |
| 2021 | SODA | Approximating the Median under the Ulam Metric. | Diptarka Chakraborty, Debarati Das, Robert Krauthgamer |
| 2021 | STOC | Subcubic algorithms for Gomory-Hu tree in unweighted graphs. | Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2021 | STOC | Towards tight bounds for spectral sparsification of hypergraphs. | Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
| 2020 | FOCS | Cut-Equivalent Trees are Optimal for Min-Cut Queries. | Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2020 | ICALP | Sketching Graphs and Combinatorial Optimization (Invited Talk). | Robert Krauthgamer |
| 2020 | ICML | Coresets for Clustering in Graphs of Bounded Treewidth. | Daniel N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu |
| 2020 | ICML | Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension. | Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Roi Sinoff |
| 2020 | SODA | New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. | Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2020 | SODA | Labelings vs. Embeddings: On Distributed Representations of Distances. | Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer |
| 2019 | FOCS | Sublinear Algorithms for Gap Edit Distance. | Elazar Goldenberg, Robert Krauthgamer, Barna Saha |
| 2019 | ICALP | Faster Algorithms for All-Pairs Bounded Min-Cuts. | Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, Daniel Wolleb-Graf |
| 2019 | ICML | Coresets for Ordered Weighted Clustering. | Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu |
| 2019 | SODA | Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems. | Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi |
| 2019 | SODA | Flow-Cut Gaps and Face Covers in Planar Graphs. | Robert Krauthgamer, James R. Lee, Havana Rika |
| 2019 | STACS | The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern. | Robert Krauthgamer, Ohad Trabelsi |
| 2018 | ICML | Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order. | Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang |
| 2017 | ICALP | Conditional Lower Bounds for All-Pairs Max-Flow. | Robert Krauthgamer, Ohad Trabelsi |
| 2017 | STOC | Streaming symmetric norms via measure concentration. | Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Lin F. Yang |
| 2016 | CPM | Color-Distance Oracles and Snippets. | Tsvi Kopelowitz, Robert Krauthgamer |
| 2016 | WG | Tight Bounds for Gomory-Hu-like Cut Counting. | Rajesh Chitnis, Lior Kamma, Robert Krauthgamer |
| 2015 | STOC | Sketching and Embedding are Equivalent for Norms. | Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn |
| 2014 | FOCS | Spectral Approaches to Nearest Neighbor Search. | Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer |
| 2014 | ICALP | Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. | Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, Shay Solomon |
| 2014 | LATIN | Multiply Balanced k -Partitioning. | Amihood Amir, Jessica Ficler, Robert Krauthgamer, Liam Roditty, Oren Sar Shalom |
| 2014 | SODA | Towards (1 + | Alexandr Andoni, Anupam Gupta, Robert Krauthgamer |
| 2014 | SODA | Cutting corners cheaply, or how to remove Steiner points. | Lior Kamma, Robert Krauthgamer, Huy L. Nguyen |
| 2014 | SODA | Non-Uniform Graph Partitioning. | Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar |
| 2013 | ALT | Adaptive Metric Dimensionality Reduction. | Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer |
| 2013 | SODA | Mimicking Networks and Succinct Representations of Terminal Cuts. | Robert Krauthgamer, Inbal Rika |
| 2013 | SPIRE | Efficient Approximation of Edit Distance. | Robert Krauthgamer |
| 2012 | FOCS | Everywhere-Sparse Spanners via Dense Subgraphs. | Eden Chlamtac, Michael Dinitz, Robert Krauthgamer |
| 2012 | ICALP | Preserving Terminal Distances Using Minors. | Robert Krauthgamer, Tamar Zondiner |
| 2012 | STOC | The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. | Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer |
| 2011 | FOCS | Streaming Algorithms via Precision Sampling. | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2011 | FOCS | Min-max Graph Partitioning and Small Set Expansion. | Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz |
| 2011 | PODC | Fault-tolerant spanners: better and simpler. | Michael Dinitz, Robert Krauthgamer |
| 2011 | SODA | A Nonlinear Approach to Dimension Reduction. | Lee-Ad Gottlieb, Robert Krauthgamer |
| 2011 | STOC | Directed spanners via flow-based linear programs. | Michael Dinitz, Robert Krauthgamer |
| 2010 | COLT | Efficient Classification for Metric Data. | Lee-Ad Gottlieb, Leonid Kontorovich, Robert Krauthgamer |
| 2010 | FOCS | Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2009 | SODA | Overcoming the | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer |
| 2009 | SODA | Approximate line nearest neighbor in high dimensions. | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen |
| 2009 | SODA | How hard is it to approximate the best Nash equilibrium? | Elad Hazan, Robert Krauthgamer |
| 2009 | SODA | Partitioning graphs into balanced components. | Robert Krauthgamer, Joseph Naor, Roy Schwartz |
| 2008 | ICALP | The Smoothed Complexity of Edit Distance. | Alexandr Andoni, Robert Krauthgamer |
| 2008 | ICDE | Greedy List Intersection. | Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, Atri Rudra |
| 2008 | SODA | Earth mover distance over high-dimensional spaces. | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer |
| 2008 | SODA | Metric clustering via consistent labeling. | Robert Krauthgamer, Tim Roughgarden |
| 2007 | FOCS | The Computational Hardness of Estimating Edit Distance [Extended Abstract]. | Alexandr Andoni, Robert Krauthgamer |
| 2007 | SODA | Estimating the sortedness of a data stream. | Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar |
| 2007 | SPAA | On triangulation of simple networks. | Robert Krauthgamer |
| 2007 | WAOA | Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations. | Robert Krauthgamer, Aranyak Mehta, Atri Rudra |
| 2006 | FOCS | Algorithms on negatively curved spaces. | Robert Krauthgamer, James R. Lee |
| 2006 | SODA | Improved lower bounds for embeddings into | Robert Krauthgamer, Yuval Rabani |
| 2004 | FOCS | Approximating Edit Distance Efficiently. | Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar |
| 2004 | FOCS | Measured Descent: A New Embedding Method for Finite Metrics. | Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor |
| 2004 | ICALP | The Black-Box Complexity of Nearest Neighbor Search. | Robert Krauthgamer, James R. Lee |
| 2004 | SODA | Approximate classification via earthmover metrics. | Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, va Tardos |
| 2004 | SODA | Navigating nets: simple algorithms for proximity search. | Robert Krauthgamer, James R. Lee |
| 2004 | SPAA | Object location in realistic networks. | Kirsten Hildrum, Robert Krauthgamer, John Kubiatowicz |
| 2003 | FOCS | Bounded Geometries, Fractals, and Low-Distortion Embeddings. | Anupam Gupta, Robert Krauthgamer, James R. Lee |
| 2003 | ISMB | Detecting protein sequence conservation via metric embeddings. | Eran Halperin, Jeremy Buhler, Richard M. Karp, Robert Krauthgamer, Ben Westover |
| 2003 | SODA | Integrality ratio for group Steiner trees and directed steiner trees. | Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang |
| 2003 | SODA | Property testing of data dimensionality. | Robert Krauthgamer, Ori Sasson |
| 2003 | STOC | Constant factor approximation of vertex-cuts in planar graphs. | Eyal Amir, Robert Krauthgamer, Satish Rao |
| 2003 | STOC | Polylogarithmic inapproximability. | Eran Halperin, Robert Krauthgamer |
| 2003 | STOC | The intrinsic dimensionality of graphs. | Robert Krauthgamer, James R. Lee |
| 2001 | SODA | On approximating the achromatic number. | Guy Kortsarz, Robert Krauthgamer |
| 2001 | STOC | Private approximation of NP-hard functions. | Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim |
| 2001 | STOC | Online server allocation in a server farm via benefit task systems. | T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko |
| 2000 | FOCS | A polylogarithmic approximation of the minimum bisection. | Uriel Feige, Robert Krauthgamer |
| 2000 | SODA | Improved classification via connectivity information. | Andrei Z. Broder, Robert Krauthgamer, Michael Mitzenmacher |
| 2000 | STOC | Approximating the minimum bisection size (extended abstract). | Uriel Feige, Robert Krauthgamer, Kobbi Nissim |