74 citations · 484 across the 77 of their papers we have counts for
100 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 m…
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…
Fast Nearest Neighbor Search for Metrics
Robert Krauthgamer, Nir Petruschka
The Nearest Neighbor Search (NNS) problem asks to design a data structure that preprocesses an -point dataset lying in a metric space , so that given a query po…