RK
Robert Krauthgamer
cs.DScs.CGmath.MGcs.LGstat.MLcs.CCmath.COmath.FAmath.STstat.TH
On Valency
published · living versionsW_yze4fmvm·v1 · currentpublished
Adversarially Robust Streaming Algorithms for -Clustering
with Chengzhi Guo, Shaofeng H. C. Jiang, David P. Woodruff, Shenghao Xie +1
1 version
W_s7efk9cd·v1published
W_99yd4ks4·v1published
W_vmq8xtgg·v1published
Preprints & journals
97 papers in the corpus · 2003–2026Coresets for -Means: When Does Uniform Sampling Suffice?2610.31491v1 · Amir Carmel, Robert Krauthgamer2026 · 0 citationsarXivon Valency
Fast Metric Decompositions in High Dimension2608.22488v1 · Robert Krauthgamer, Asaf Petruschka, Nir Petruschka2026 · 0 citationsarXiv
Towards Lower Bounds for Geometric Spanners in High Dimension2608.08706v1 · Robert Krauthgamer, Nir Petruschka2026 · 0 citationsarXiv
Fully Dynamic Edge Connectivity in Time2607.10689v2 · Yotam Kenneth-Mordoch, Robert Krauthgamer2026 · 0 citationsarXiv
Optimal Stable Coresets for Geometric Median via Uniform Sampling2606.30348v1 · Amir Carmel, Robert Krauthgamer, Nir Petruschka2026 · 0 citationsAPPROX 2026
Fast Nearest Neighbor Search for Metrics2603.21148v1 · Robert Krauthgamer, Nir Petruschka2026 · 0 citationsarXiv
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow2511.10036v2 · Yotam Kenneth-Mordoch, Robert Krauthgamer2025 · 0 citationsarXiv
All-Pairs Minimum Cut using Cut Queries2510.16741v1 · Yotam Kenneth-Mordoch, Robert Krauthgamer2025 · 0 citationsarXiv
Stable coresets: Unleashing the power of uniform sampling2509.22189v2 · Amir Carmel, Robert Krauthgamer2025 · 0 citationsarXiv
Dimension Reduction for Clustering: The Curious Case of Discrete Centers2509.07444v1 · Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir et al.2025 · 0 citationsarXiv
The Expiration Streaming Model: Diameter, -Center, Counting, Sampling, and Friends2509.07587v2 · Lotte Blank, Sergio Cabello, MohammadTaghi Hajiaghayi et al.2025 · 0 citationsarXiv
Simple Algorithms for Fully Dynamic Edge Connectivity2508.07783v2 · Yotam Kenneth-Mordoch, Robert Krauthgamer2025 · 0 citationsarXiv
The Power of Recursive Embeddings for Metrics2503.18508v2 · Robert Krauthgamer, Nir Petruschka, Shay Sapir2025 · 0 citationsarXiv
Lipschitz Decompositions of Finite Metrics2502.01120v1 · Robert Krauthgamer, Nir Petruschka2025 · 0 citationsarXiv
Near-Optimal Dimension Reduction for Facility Location2411.05432v1 · Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer et al.2024 · 1 citationarXiv
Moderate Dimension Reduction for -Center Clustering2312.01391v6 · Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir2023 · 1 citationPublished at SoCG 2024
Fully Scalable MPC Algorithms for Clustering in High Dimension2307.07848v3 · Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang et al.2023 · 1 citationarXiv
Lower Bounds for Pseudo-Deterministic Counting in a Stream2303.16287v2 · Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan et al.2023 · 3 citationsarXiv
Clustering Permutations: New Techniques with Streaming Applications2212.01821v1 · Diptarka Chakraborty, Debarati Das, Robert Krauthgamer2022 · 2 citationsarXiv
An Algorithmic Bridge Between Hamming and Levenshtein Distances2211.12496v1 · Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer et al.2022 · 2 citationsarXiv
Streaming Euclidean Max-Cut: Dimension vs Data Reduction2211.05293v2 · Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer2022 · 4 citationsarXiv
Recovery Guarantees for Distributed-OMP2209.07230v2 · Chen Amiraz, Robert Krauthgamer, Boaz Nadler2022 · 0 citationsarXiv
The Power of Uniform Sampling for Coresets2209.01901v2 · Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang et al.2022 · 20 citationsarXiv
Exact Flow Sparsification Requires Unbounded Size2207.07363v2 · Robert Krauthgamer, Ron Mosenzon2022 · 1 citationarXiv
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs2207.01459v1 · Itai Boneh, Robert Krauthgamer2022 · 1 citationarXiv
Near-Linear -Emulators for Planar Graphs2206.10681v1 · Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan2022 · 0 citationsarXiv
Streaming Facility Location in High Dimension via Geometric Hashing2204.02095v5 · Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang et al.2022 · 11 citationsarXiv
Comparison of Matrix Norm Sparsification2201.12874v3 · Robert Krauthgamer, Shay Sapir2022 · 2 citationsarXiv
Flow Metrics on Graphs2112.06916v1 · Lior Kalman, Robert Krauthgamer2021 · 2 citationsarXiv
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal2111.12706v2 · Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer et al.2021 · 5 citationsarXiv
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time2111.04958v3 · Amir Abboud, Robert Krauthgamer, Jason Li et al.2021 · 17 citationsarXiv
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees2110.15891v1 · Amir Abboud, Robert Krauthgamer, Ohad Trabelsi2021 · 7 citationsarXiv
Coresets for Kernel Clustering2110.02898v5 · Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou et al.2021 · 2 citationsarXiv
Approximate Trace Reconstruction via Median String (in Average-Case)2107.09497v1 · Diptarka Chakraborty, Debarati Das, Robert Krauthgamer2021 · 4 citationsarXiv
Coresets for Clustering with Missing Values2106.16112v3 · Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer et al.2021 · 2 citationsarXiv
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time2106.02981v1 · Amir Abboud, Robert Krauthgamer, Ohad Trabelsi2021 · 13 citationsarXiv
Spectral Hypergraph Sparsifiers of Nearly Linear Size2106.02353v1 · Michael Kapralov, Robert Krauthgamer, Jakab Tardos et al.2021 · 14 citationsarXiv
Smoothness of Schatten Norms and Sliding-Window Matrix Streams2103.08211v2 · Robert Krauthgamer, Shay Sapir2021 · 0 citationsarXiv
Distributed Sparse Normal Means Estimation with Sublinear Communication2102.03060v2 · Chen Amiraz, Robert Krauthgamer, Boaz Nadler2021 · 0 citationsarXiv
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs2012.10281v2 · Amir Abboud, Robert Krauthgamer, Ohad Trabelsi2020 · 23 citationsarXiv
Towards Tight Bounds for Spectral Sparsification of Hypergraphs2011.06530v2 · Michael Kapralov, Robert Krauthgamer, Jakab Tardos et al.2020 · 18 citationsarXiv
Streaming Algorithms for Geometric Steiner Forest2011.04324v4 · Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer et al.2020 · 1 citationarXiv
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices2011.01777v2 · Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan et al.2020 · 2 citationsarXiv
Approximating the Median under the Ulam Metric2011.00868v1 · Diptarka Chakraborty, Debarati Das, Robert Krauthgamer2020 · 3 citationsarXiv
Cut-Equivalent Trees are Optimal for Min-Cut Queries2009.06090v1 · Amir Abboud, Robert Krauthgamer, Ohad Trabelsi2020 · 20 citationsarXiv
Coresets for Clustering in Excluded-minor Graphs and Beyond2004.07718v2 · Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer et al.2020 · 20 citationsarXiv
Faster Algorithms for Orienteering and -TSP2002.07727v2 · Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika2020 · 4 citationsarXiv
Sublinear Algorithms for Gap Edit Distance1910.00901v1 · Elazar Goldenberg, Robert Krauthgamer, Barna Saha2019 · 19 citationsarXiv
Labelings vs. Embeddings: On Distributed Representations of Distances1907.06857v2 · Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer2019 · 4 citationsarXiv
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension1907.05457v2 · Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan et al.2019 · 7 citationsarXiv
Career total: 263 works. 97 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.