28 citations · 70 across the 20 of their papers we have counts for
4 papers · 1 filter
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…
Optimizing Budget Allocation in Graphs
Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb +1
In the classical facility location problem we consider a graph with fixed weights on the edges of . The goal is then to find an optimal positioning for a set of facilities o…
Near-optimal sample compression for nearest neighbors
Lee-Ad Gottlieb, Aryeh Kontorovich, Pinhas Nisnevitch
We present the first sample compression algorithm for nearest neighbors with non-trivial performance guarantees. We complement these guarantees by demonstrating almost matching har…
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…