Skip to content

Author

Robert Krauthgamer

We have 6 of 216 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

Coresets for $k$-Means: When Does Uniform Sampling Suffice?

Data summarization techniques, such as coresets, are essential for scaling clustering algorithms to massive datasets. We study uniform sampling, which is an extremely simple and ultra-efficient method to construct coresets, in the context of weak, stable, and strong coresets for the $k$-means problem in Hilbert space....

Amir Carmel, Robert Krauthgamer · 0 citations
Preprint Oct 2026

Dimension Reduction and Coresets for Min-Sum $k$-Clustering

The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two st...

Asaf Dallal, Robert Krauthgamer · 0 citations
Preprint Nov 2026

Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering

We design adversarially robust algorithms for dynamic geometric streams that $(1 + \epsilon)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(\epsilon^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk...

Cheng-Zhi Guo, S. Jiang, Robert Krauthgamer et al. · 0 citations
Preprint Aug 2026

Towards Lower Bounds for Geometric Spanners in High Dimension

We study the stretch--size tradeoff for geometric spanners in high-dimensional $\ell_p$ spaces. Our main contribution is a simple proof of a lower bound shown by Har-Peled, Indyk, and Sidiropoulos [SODA 2013]: Every $2$-hop $t$-spanner of the pointset $\{0,1\}^d$ under $\ell_2$ norm has at least $(2^d)^{1+\Omega(1/t^2)...

Robert Krauthgamer, Nir Petruschka · 0 citations
Conference Aug 2026

Fast Metric Decompositions in High Dimension

The algorithm constructs a new sparse neighborhood cover that is based on geometric properties of $\ell_\infty$ and utilizes recent reductions between covers and decompositions, and the techniques have additional applications to spanners and nearest-neighbor search.

Robert Krauthgamer, Asaf Petruschka, Nir Petruschka · 0 citations
Preprint Jul 2026

Fully Dynamic Edge Connectivity in $\tilde{O}(n^{12/13})$ Time

This work designs a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\tilde{O}(n^{12/13})$ for all values of $\lambda_G$.

Yotam Kenneth-Mordoch, Robert Krauthgamer · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.