Lee-Ad Gottlieb

activity

20092025

most citedThe Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme

28 citations · 70 across the 20 of their papers we have counts for

collaborators

28 papers

cs.DS2025

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$ -clustering and their fair variants

Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb +1

We provide improved upper and lower bounds for the Min-Sum-Radii (MSR) and Min-Sum-Diameters (MSD) clustering problems with a bounded number of clusters $k$ . In particular, we prop…

cs.LG2023

Weighted Distance Nearest Neighbor Condensing

Lee-Ad Gottlieb, Timor Sharabi, Roi Weiss

The problem of nearest neighbor condensing has enjoyed a long history of study, both in its theoretical and practical aspects. In this paper, we introduce the problem of weighted d…

cs.LG2023

Using Deepfake Technologies for Word Emphasis Detection

Eran Kaufman, Lee-Ad Gottlieb

In this work, we consider the task of automated emphasis detection for spoken language. This problem is challenging in that emphasis is affected by the particularities of speech of…

math.MG2020

Non-uniform packings

Lee-Ad Gottlieb, Aryeh Kontorovich

We generalize the classical notion of packing a set by balls with identical radii to the case where the radii may be different. The largest number of such balls that fit inside the…

math.ST2020★ 3 cited

Functions with average smoothness: structure, algorithms, and learning

Yair Ashlagi, Lee-Ad Gottlieb, Aryeh Kontorovich

We initiate a program of average smoothness analysis for efficiently learning real-valued functions on metric spaces. Rather than using the Lipschitz constant as the regularizer, w…

cs.LG2020

Nested Barycentric Coordinate System as an Explicit Feature Map

Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich +2

We propose a new embedding method which is particularly well-suited for settings where the sample size greatly exceeds the ambient dimension. Our technique consists of partitioning…

cs.LG2020

Apportioned Margin Approach for Cost Sensitive Large Margin Classifiers

Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich

We consider the problem of cost sensitive multiclass classification, where we would like to increase the sensitivity of an important class at the expense of a less important one. W…

cs.DS2020

Faster Algorithms for Orienteering and $k$ -TSP

Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika

We consider the rooted orienteering problem in Euclidean space: Given $n$ points $P$ in $R^{d}$ , a root point $s \in P$ and a budget $B > 0$ , find a path that starts fr…

cs.LG2019★ 1 cited

Classification in asymmetric spaces via sample compression

Lee-Ad Gottlieb, Shira Ozeri

We initiate the rigorous study of classification in quasi-metric spaces. These are point sets endowed with a distance function that is non-negative and also satisfies the triangle…

cs.DS2019

Labelings vs. Embeddings: On Distributed Representations of Distances

Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer

We investigate for which metric spaces the performance of distance labeling and of $ℓ_{\infty}$ -embeddings differ, and how significant can this difference be. Recall that a distan…

cs.CG2019★ 1 cited

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 $(1 + ε)$ -approximate Steiner forest in near-linear time $n \cdot 2^{(1/ ε)^{O (dd i m^{2})} (l o g l o g n)^{2}}$ . This is a dramatic improvement upon the…

cs.LG2018

Learning convex polyhedra with margin

Lee-Ad Gottlieb, Eran Kaufman, Aryeh Kontorovich +1

We present an improved algorithm for {\em quasi-properly} learning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consi…

cs.CG2015★ 2 cited

Approximate nearest neighbor search for $ℓ_{p}$ -spaces ( $2 < p < \infty$ ) via embeddings

Yair Bartal, Lee-Ad Gottlieb

While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and $ℓ_{1}$ , few non-trivial algorithms are known for $ℓ_{p}$ when ($2 < p < \i…

cs.CG2015★ 9 cited

A light metric spanner

Lee-Ad Gottlieb

It has long been known that $d$ -dimensional Euclidean point sets admit $(1 + ε)$ -stretch spanners with lightness $W_{E} = ε^{- O (d)}$ , that is total edge weight at most $W_{E}$ times the…

cs.LG2015★ 3 cited

Nearly optimal classification for semimetrics

Lee-Ad Gottlieb, Aryeh Kontorovich

We initiate the rigorous study of classification in semimetric spaces, which are point sets with a distance function that is non-negative and symmetric, but need not satisfy the tr…

cs.CG2014★ 1 cited

Dimension reduction techniques for $ℓ_{p}$ , $1 \leq p \leq 2$ , with applications

Yair Bartal, Lee-Ad Gottlieb

For Euclidean space ( $ℓ_{2}$ ), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss, with a host of known applications. Here, we consider the probl…

cs.DS2014

Optimizing Budget Allocation in Graphs

Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb +1

In the classical facility location problem we consider a graph $G$ with fixed weights on the edges of $G$ . The goal is then to find an optimal positioning for a set of facilities o…

cs.LG2014

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…

cs.CG2014

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…

cs.CG2013★ 1 cited

On the Impossibility of Dimension Reduction for Doubling Subsets of $ℓ_{p}$ , $p > 2$

Yair Bartal, Lee-Ad Gottlieb, Ofer Neiman

A major open problem in the field of metric embedding is the existence of dimension reduction for $n$ -point subsets of Euclidean space, such that both distortion and dimension depe…

cs.LG2013

Efficient Classification for Metric Data

Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer

Recent advances in large-margin classification of data residing in general metric spaces (rather than Hilbert spaces) enable classification under various natural metrics, such as s…

cs.LG2013

Adaptive Metric Dimensionality Reduction

Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer

We study adaptive data-dependent dimensionality reduction in the context of supervised learning in general metric spaces. Our main statistical contribution is a generalization boun…

cs.CC2011★ 28 cited

The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme

Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+ep…

cs.LG2011

Efficient Regression in Metric Spaces via Approximate Lipschitz Extension

Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer

We present a framework for performing efficient regression in general metric spaces. Roughly speaking, our regressor predicts the value at a new point by computing a Lipschitz exte…

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters k-clustering and their fair variants

Weighted Distance Nearest Neighbor Condensing

Using Deepfake Technologies for Word Emphasis Detection

Non-uniform packings

Functions with average smoothness: structure, algorithms, and learning

Nested Barycentric Coordinate System as an Explicit Feature Map

Apportioned Margin Approach for Cost Sensitive Large Margin Classifiers

Faster Algorithms for Orienteering and k-TSP

Classification in asymmetric spaces via sample compression

Labelings vs. Embeddings: On Distributed Representations of Distances

Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces

Learning convex polyhedra with margin

Approximate nearest neighbor search for ℓp​-spaces (2<p<∞) via embeddings

A light metric spanner

Nearly optimal classification for semimetrics

Dimension reduction techniques for ℓp​, 1≤p≤2, with applications

Optimizing Budget Allocation in Graphs

Near-optimal sample compression for nearest neighbors

Light spanners for snowflake metrics

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp​, p>2

Efficient Classification for Metric Data

Adaptive Metric Dimensionality Reduction

The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme

Efficient Regression in Metric Spaces via Approximate Lipschitz Extension

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$ -clustering and their fair variants

Faster Algorithms for Orienteering and $k$ -TSP

Approximate nearest neighbor search for $ℓ_{p}$ -spaces ( $2 < p < \infty$ ) via embeddings

Dimension reduction techniques for $ℓ_{p}$ , $1 \leq p \leq 2$ , with applications

On the Impossibility of Dimension Reduction for Doubling Subsets of $ℓ_{p}$ , $p > 2$