Robert Krauthgamer

ORCID

Publication Activity (10 Years)

Years Active: 1997-2024
Publications (10 Years): 131

Top Venues

Publications

Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
Fully-Scalable MPC Algorithms for Clustering in High Dimension. ICALP (2024)
Chen Amiraz, Robert Krauthgamer, Boaz Nadler
Recovery Guarantees for Distributed-OMP. AISTATS (2024)
Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
Labelings vs. Embeddings: On Distributed and Prioritized Representations of Distances. Discret. Comput. Geom. 71 (3) (2024)
Yotam Kenneth, Robert Krauthgamer
Cut Sparsification and Succinct Representation of Submodular Hypergraphs. ICALP (2024)
Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, Yubo Zhang
Coresets for kernel clustering. Mach. Learn. 113 (8) (2024)
Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir
Moderate Dimension Reduction for k-Center Clustering. SoCG (2024)
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
Lower Bounds for Pseudo-Deterministic Counting in a Stream. CoRR (2023)
Robert Krauthgamer, Ron Mosenzon
Exact Flow Sparsification Requires Unbounded Size. SODA (2023)
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
Lower Bounds for Pseudo-Deterministic Counting in a Stream. ICALP (2023)
Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir
Moderate Dimension Reduction for k-Center Clustering. CoRR (2023)
Yotam Kenneth, Robert Krauthgamer
Cut Sparsification and Succinct Representation of Submodular Hypergraphs. CoRR (2023)
Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer
Streaming Euclidean Max-Cut: Dimension vs Data Reduction. STOC (2023)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Clustering Permutations: New Techniques with Streaming Applications. ITCS (2023)
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
Fully Scalable MPC Algorithms for Clustering in High Dimension. CoRR (2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
An Algorithmic Bridge Between Hamming and Levenshtein Distances. ITCS (2023)
Robert Krauthgamer, Shay Sapir
Comparison of Matrix Norm Sparsification. Algorithmica 85 (12) (2023)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. FOCS (2022)
Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika
-TSP. Theor. Comput. Sci. 914 (2022)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
An Algorithmic Bridge Between Hamming and Levenshtein Distances. CoRR (2022)
Chen Amiraz, Robert Krauthgamer, Boaz Nadler
Distributed Sparse Linear Regression with Sublinear Communication. CoRR (2022)
Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, Mingwei Yang
Streaming Facility Location in High Dimension via New Geometric Hashing. CoRR (2022)
Robert Krauthgamer, Shay Sapir
Smoothness of Schatten norms and sliding-window matrix streams. Inf. Process. Lett. 177 (2022)
Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
Streaming Algorithms for Geometric Steiner Forest. ICALP (2022)
Robert Krauthgamer, Ron Mosenzon
Exact Flow Sparsification Requires Unbounded Size. CoRR (2022)
Robert Krauthgamer, Shay Sapir
Comparison of Matrix Norm Sparsification. CoRR (2022)
Yu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer
Streaming Euclidean Max-Cut: Dimension vs Data Reduction. CoRR (2022)
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
Near-Linear ε-Emulators for Planar Graphs. CoRR (2022)
Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, Mingwei Yang
Streaming Facility Location in High Dimension via Geometric Hashing. FOCS (2022)
Vladimir Braverman, Robert Krauthgamer, Lin F. Yang
Universal Streaming of Subset Norms. Theory Comput. 18 (2022)
Robert Krauthgamer, David Reitblat
Almost-Smooth Histograms and Sliding-Window Graph Algorithms. Algorithmica 84 (10) (2022)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. SODA (2022)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. FOCS (2022)
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu
The Power of Uniform Sampling for Coresets. FOCS (2022)
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu
The Power of Uniform Sampling for Coresets. CoRR (2022)
Itai Boneh, Robert Krauthgamer
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs. CoRR (2022)
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
-emulators for planar graphs. STOC (2022)
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
Spectral Hypergraph Sparsifiers of Nearly Linear Size. FOCS (2022)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Clustering Permutations: New Techniques with Streaming Applications. CoRR (2022)
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. FOCS (2022)
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
Towards tight bounds for spectral sparsification of hypergraphs. STOC (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Subcubic algorithms for Gomory-Hu tree in unweighted graphs. STOC (2021)
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Coresets for Clustering in Excluded-minor Graphs and Beyond. SODA (2021)
Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, Yubo Zhang
Coresets for Kernel Clustering. CoRR (2021)
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
Spectral Hypergraph Sparsifiers of Nearly Linear Size. FOCS (2021)
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi
Gomory-Hu Tree in Subcubic Time. CoRR (2021)
Lior Kalman, Robert Krauthgamer
Flow Metrics on Graphs. CoRR (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. CoRR (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees. CoRR (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. FOCS (2021)
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
Spectral Hypergraph Sparsifiers of Nearly Linear Size. CoRR (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. Theory Comput. 17 (2021)
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Coresets for Clustering with Missing Values. NeurIPS (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximate Trace Reconstruction via Median String (In Average-Case). FSTTCS (2021)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. CoRR (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximating the Median under the Ulam Metric. SODA (2021)
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices. COLT (2021)
Chen Amiraz, Robert Krauthgamer, Boaz Nadler
Sparse Normal Means Estimation with Sublinear Communication. CoRR (2021)
Robert Krauthgamer, Shay Sapir
Smoothness of Schatten Norms and Sliding-Window Matrix Streams. CoRR (2021)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximate Trace Reconstruction via Median String (in Average-Case). CoRR (2021)
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Coresets for Clustering with Missing Values. CoRR (2021)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Cut-Equivalent Trees are Optimal for Min-Cut Queries. CoRR (2020)
Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý
Streaming Algorithms for Geometric Steiner Forest. CoRR (2020)
Daniel N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Coresets for Clustering in Graphs of Bounded Treewidth. ICML (2020)
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Roi Sinoff
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension. ICML (2020)
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Coresets for Clustering in Excluded-minor Graphs and Beyond. CoRR (2020)
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices. CoRR (2020)
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximating the Median under the Ulam Metric. CoRR (2020)
Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika
Faster Algorithms for Orienteering and k-TSP. CoRR (2020)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs. CoRR (2020)
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida
Towards Tight Bounds for Spectral Sparsification of Hypergraphs. CoRR (2020)
Robert Krauthgamer
Sketching Graphs and Combinatorial Optimization (Invited Talk). ICALP (2020)
Robert Krauthgamer, Havana Rika
Refined Vertex Sparsifiers of Planar Graphs. SIAM J. Discret. Math. 34 (1) (2020)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Cut-Equivalent Trees are Optimal for Min-Cut Queries. FOCS (2020)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. SODA (2020)
Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
Labelings vs. Embeddings: On Distributed Representations of Distances. SODA (2020)
Robert Krauthgamer
Sketching Graphs and Combinatorial Optimization (Invited Talk). FSTTCS (2019)
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
Sublinear Algorithms for Gap Edit Distance. FOCS (2019)
Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
On Solving Linear Systems in Sublinear Time. ITCS (2019)
Robert Krauthgamer, Ohad Trabelsi
The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern. STACS (2019)
Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer
Labelings vs. Embeddings: On Distributed Representations of Distances. CoRR (2019)
Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, Daniel Wolleb-Graf
Faster Algorithms for All-Pairs Bounded Min-Cuts. ICALP (2019)
Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Coresets for Clustering in Graphs of Bounded Treewidth. CoRR (2019)
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. CoRR (2019)
Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
Relaxed Voronoi: A Simple Framework for Terminal-Clustering Problems. SOSA (2019)
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Coresets for Ordered Weighted Clustering. ICML (2019)
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
Sublinear Algorithms for Gap Edit Distance. CoRR (2019)
Robert Krauthgamer, James R. Lee, Havana Rika
Flow-Cut Gaps and Face Covers in Planar Graphs. SODA (2019)
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Coresets for Ordered Weighted Clustering. CoRR (2019)
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Roi Sinoff
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension. CoRR (2019)
Robert Krauthgamer, David Reitblat
Almost-Smooth Histograms and Sliding-Window Graph Algorithms. CoRR (2019)
Amir Abboud, Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski
Faster Algorithms for All-Pairs Bounded Min-Cuts. CoRR (2018)
Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems. CoRR (2018)
Robert Krauthgamer, James R. Lee, Havana Rika
Flow-Cut Gaps and Face Covers in Planar Graphs. CoRR (2018)
Alexandr Andoni, Lior Kamma, Robert Krauthgamer, Eric Price
Batch Sparse Recovery, or How to Leverage the Average Sparsity. CoRR (2018)
Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn
Sketching and Embedding are Equivalent for Norms. SIAM J. Comput. 47 (3) (2018)
Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order. ICML (2018)
Robert Krauthgamer, Ohad Trabelsi
Conditional Lower Bounds for All-Pairs Max-Flow. ACM Trans. Algorithms 14 (4) (2018)
Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow
On Solving Linear Systems in Sublinear Time. CoRR (2018)
Artur Czumaj, Robert Krauthgamer
3rd Highlights of Algorithms (HALG 2018). SIGACT News 49 (3) (2018)
Artur Czumaj, Robert Krauthgamer
Report on HALG 2018. Bull. EATCS 126 (2018)

Robert Krauthgamer.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Robert Krauthgamer