1 citations · 1 across the 4 of their papers we have counts for
17 papers
Fast Metric Decompositions in High Dimension
Robert Krauthgamer, Asaf Petruschka, Nir Petruschka
Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of -…
Recovery Beats Storage: Improved Space for Preprocessed 3SUM
Amir Carmel, Yakov Kosoburd, Robert Krauthgamer
The 3SUM problem asks, given sets of integers, whether there exist and whose sum belongs to . In the preprocessed variant with unknown , one preproc…
Towards Lower Bounds for Geometric Spanners in High Dimension
Robert Krauthgamer, Nir Petruschka
We study the stretch--size tradeoff for geometric spanners in high-dimensional spaces. Our main contribution is a simple proof of a lower bound shown by Har-Peled, Indyk,…
Fully Dynamic Edge Connectivity in Time
Yotam Kenneth-Mordoch, Robert Krauthgamer
In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity of an -vertex graph that undergoes edge insertions and deletions. Our…
Moderate Dimension Reduction for -Center Clustering
Shaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir
The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension reduction via a random linear map, which has become a fundamental technique in many computational settings.…
Optimal Stable Coresets for Geometric Median via Uniform Sampling
Amir Carmel, Robert Krauthgamer, Nir Petruschka
The geometric median problem asks to find a point in that minimizes the sum of Euclidean distances to an input set. It is a classical problem in computational geomet…