48 citations · 79 across the 36 of their papers we have counts for
7 papers · 1 filter
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…
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 -approximate Earth Mover's Distance (EMD) to -approximate Closest Pair (CP). As a consequence, we improve the fastest kno…
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…
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…
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…
Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
Nicolas Menand, Erik Waingarten
Given a set of vectors , the Euclidean max-cut problem asks to partition the vectors into two parts so as to maximize the sum of Eucl…
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 in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio~\cite{CRS1…