14 papers
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…
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
Yotam Kenneth-Mordoch, Robert Krauthgamer
All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to find a minimum -cut for every pair of vertices . A recent line of work on fast algorithms for APM…
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…