Erik Waingarten

activity

20162026

most citedOptimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

48 citations · 79 across the 36 of their papers we have counts for

collaborators

39 papers

cs.DS2026

Learning Partition Trees for Nearest Neighbor Search

Sanjeev Khanna, Ashwin Padaki, Erik Waingarten

We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset $P \subset R^{d}$ of size $n$ and sample access to a query distributio…

cs.DS2026

Locally Approximating the Top Eigenvector of Bounded Entry Matrices

Nicolas Menand, Erik Waingarten

We provide a local computation algorithm to approximate the top eigenvector $x \in R^{n}$ of a symmetric matrix $A \in R^{n \times n}$ with entries between $- 1$ and…

cs.DS2026

Prune, Don't Rebuild: Efficiently Tuning $α$ -Reachable Graphs for Nearest Neighbor Search

Tian Zhang, Ashwin Padaki, Jiaming Liang +2

Vector similarity search is an essential primitive in modern AI and ML applications. Most vector databases adopt graph-based approximate nearest neighbor (ANN) search algorithms, s…

cs.DS2025

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams

Sanjeev Khanna, Ashwin Padaki, Krish Singal +1

We study the space complexity of estimating the diameter of a subset of points in an arbitrary metric space in the dynamic (turnstile) streaming model. The input is given as a stre…

cs.DS2025

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair

Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram +1

We give a reduction from $(1 + ε)$ -approximate Earth Mover's Distance (EMD) to $(1 + ε)$ -approximate Closest Pair (CP). As a consequence, we improve the fastest kno…

cs.DS2025

Instance-Optimal Uniformity Testing and Tracking

Guy Blanc, Clément L. Canonne, Erik Waingarten

In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the unifo…

cs.DS2025

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness

Sanjeev Khanna, Ashwin Padaki, Erik Waingarten

We initiate the study of approximation algorithms and computational barriers for constructing sparse $α$ -navigable graphs [IX23, DGM+24], a core primitive underlying recent advance…

cs.DS2025

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

Jie Gao, Rajesh Jayaram, Benedikt Kolbe +4

Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction…

cs.DS2025

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut

Nicolas Menand, Erik Waingarten

Given a set of vectors $X = {x_{1}, \dots, x_{n}} \subset R^{d}$ , the Euclidean max-cut problem asks to partition the vectors into two parts so as to maximize the sum of Eucl…

math.ST2025

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

Deeparnab Chakrabarty, Xi Chen, Simeon Ristic +2

We study monotonicity testing of high-dimensional distributions on ${- 1, 1}^{n}$ in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio~\cite{CRS1…

cs.DM2024

Nearly Tight Bounds on Testing of Metric Properties

Yiqiao Bao, Sampath Kannan, Erik Waingarten

Given a non-negative $n \times n$ matrix viewed as a set of distances between $n$ points, we consider the property testing problem of deciding if it is a metric. We also consider t…

cs.DS2024

Average-Distortion Sketching

Yiqiao Bao, Anubhav Baweja, Nicolas Menand +3

We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwis…

cs.CC2024

Lower Bounds for Convexity Testing

Xi Chen, Anindya De, Shivam Nadimpalli +2

We consider the problem of testing whether an unknown and arbitrary set $S \subseteq R^{n}$ (given as a black-box membership oracle) is convex, versus $ε$ -far from…

cs.DS2024

Data-Dependent LSH for the Earth Mover's Distance

Rajesh Jayaram, Erik Waingarten, Tian Zhang

We give new data-dependent locality sensitive hashing schemes (LSH) for the Earth Mover's Distance ( $EMD$ ), and as a result, improve the best approximation for nearest nei…

cs.DS2024

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations

Moses Charikar, Michael Kapralov, Erik Waingarten

In the kernel density estimation (KDE) problem one is given a kernel $K (x, y)$ and a dataset $P$ of points in a Euclidean space, and must prepare a data structure that can quickly…

cs.LG2023

Simple, Scalable and Effective Clustering via One-Dimensional Projections

Moses Charikar, Monika Henzinger, Lunjia Hu +2

Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and $k$ -means+…

cs.DS2023

Fast Algorithms for a New Relaxation of Optimal Transport

Moses Charikar, Beidi Chen, Christopher Re +1

We introduce a new class of objectives for optimal transport computations of datasets in high-dimensional Euclidean spaces. The new objectives are parametrized by $ρ \geq 1$ , and pr…

cs.DS2023★ 5 cited

A Near-Linear Time Algorithm for the Chamfer Distance

Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram +2

For any two point sets $A, B \subset R^{d}$ of size up to $n$ , the Chamfer distance from $A$ to $B$ is defined as $CH (A, B) = \sum_{a \in A} min_{b \in B} d_{X} (a, b)$ , whe…

cs.DS2022

Streaming Euclidean MST to a Constant Factor

Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram +2

We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an $n$ -point set $X \subset R^{d}$ .…

cs.DS2022★ 1 cited

Estimation of Entropy in Constant Space with Improved Sample Complexity

Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson +1

Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the entropy of a distribution $D$ over an alphabet of size $k$ up to $\pm ε$ additive error by streaming…

cs.DS2022★ 3 cited

The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction

Moses Charikar, Erik Waingarten

We study the effect of Johnson-Lindenstrauss transforms in various projective clustering problems, generalizing recent results which only applied to center-based clustering [MMR19]…

cs.DS2022

Polylogarithmic Sketches for Clustering

Moses Charikar, Erik Waingarten

Given $n$ points in $ℓ_{p}^{d}$ , we consider the problem of partitioning points into $k$ clusters with associated centers. The cost of a clustering is the sum of $p^{th}$ pow…

cs.DS2021

New Streaming Algorithms for High Dimensional EMD and MST

Xi Chen, Rajesh Jayaram, Amit Levi +1

We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an $n$ -point set $X \subset {1, 2, \dots, Δ}^{d}$ , and com…

cs.DS2020★ 6 cited

Learning and Testing Junta Distributions with Subcube Conditioning

Xi Chen, Rajesh Jayaram, Amit Levi +1

We study the problems of learning and testing junta distributions on ${- 1, 1}^{n}$ with respect to the uniform distribution, where a distribution $p$ is a $k$ -junta if its probabili…

Learning Partition Trees for Nearest Neighbor Search

Locally Approximating the Top Eigenvector of Bounded Entry Matrices

Prune, Don't Rebuild: Efficiently Tuning α-Reachable Graphs for Nearest Neighbor Search

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair

Instance-Optimal Uniformity Testing and Tracking

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

Nearly Tight Bounds on Testing of Metric Properties

Average-Distortion Sketching

Lower Bounds for Convexity Testing

Data-Dependent LSH for the Earth Mover's Distance

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations

Simple, Scalable and Effective Clustering via One-Dimensional Projections

Fast Algorithms for a New Relaxation of Optimal Transport

A Near-Linear Time Algorithm for the Chamfer Distance

Streaming Euclidean MST to a Constant Factor

Estimation of Entropy in Constant Space with Improved Sample Complexity

The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction

Polylogarithmic Sketches for Clustering

New Streaming Algorithms for High Dimensional EMD and MST

Learning and Testing Junta Distributions with Subcube Conditioning

Prune, Don't Rebuild: Efficiently Tuning $α$ -Reachable Graphs for Nearest Neighbor Search