28 citations · 70 across the 20 of their papers we have counts for
7 papers · 1 filter
Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces
Lee-Ad Gottlieb, Yair Bartal
We give an algorithm that computes a -approximate Steiner forest in near-linear time . This is a dramatic improvement upon the…
Approximate nearest neighbor search for -spaces () via embeddings
Yair Bartal, Lee-Ad Gottlieb
While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and , few non-trivial algorithms are known for when ($2 < p < \i…
A light metric spanner
Lee-Ad Gottlieb
It has long been known that -dimensional Euclidean point sets admit -stretch spanners with lightness , that is total edge weight at most times the…
Dimension reduction techniques for , , with applications
Yair Bartal, Lee-Ad Gottlieb
For Euclidean space (), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss, with a host of known applications. Here, we consider the probl…
Light spanners for snowflake metrics
Lee-Ad Gottlieb, Shay Solomon
A classic result in the study of spanners is the existence of light low-stretch spanners for Euclidean spaces. These spanners ahve arbitrary low stretch, and weight only a constant…
On the Impossibility of Dimension Reduction for Doubling Subsets of ,
Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman
A major open problem in the field of metric embedding is the existence of dimension reduction for -point subsets of Euclidean space, such that both distortion and dimension depe…
A Nonlinear Approach to Dimension Reduction
Lee-Ad Gottlieb, Robert Krauthgamer
The flattening lemma of Johnson and Lindenstrauss [JL84] is a powerful tool for dimension reduction. It has been conjectured that the target dimension bounds can be refined a…