6 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 -…
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,…
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…
The Power of Recursive Embeddings for Metrics
Robert Krauthgamer, Nir Petruschka, Shay Sapir
Metric embedding is a powerful tool used extensively in mathematics and computer science. We devise a new method of using metric embeddings recursively, which turns out to be parti…
Lipschitz Decompositions of Finite Metrics
Robert Krauthgamer, Nir Petruschka
Lipschitz decomposition is a useful tool in the design of efficient algorithms involving metric spaces. While many bounds are known for different families of finite metrics, the op…