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

Showing cs.DSShow all

30 papers · 1 filter

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…

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.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.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…

cs.DS2019

Optimal Adaptive Detection of Monotone Patterns

Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten

We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed $2 \leq k \in N$ and $ε > 0$ , consider the problem of findi…

cs.DS2019

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

Clément L. Canonne, Xi Chen, Gautam Kamath +2

We give a nearly-optimal algorithm for testing uniformity of distributions supported on ${- 1, 1}^{n}$ , which makes $O ~ (n / ε^{2})$ queries to a subcube condition…

cs.DS2019

Approximating the Distance to Monotonicity of Boolean Functions

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten

We design a nonadaptive algorithm that, given oracle access to a function $f : {0, 1}^{n} \to {0, 1}$ which is $α$ -far from monotone, makes poly $(n, 1/ α)$ queries and returns an est…

cs.DS2019★ 4 cited

Finding monotone patterns in sublinear time

Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter +1

We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed $k \in N$ and $ε > 0$ , we show that the n…

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

Average-Distortion Sketching

Data-Dependent LSH for the Earth Mover's Distance

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations

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

Optimal Adaptive Detection of Monotone Patterns

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

Approximating the Distance to Monotonicity of Boolean Functions

Finding monotone patterns in sublinear time

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