48 citations · 79 across the 36 of their papers we have counts for
5 papers · 1 filter
Nearly Tight Bounds on Testing of Metric Properties
Yiqiao Bao, Sampath Kannan, Erik Waingarten
Given a non-negative matrix viewed as a set of distances between points, we consider the property testing problem of deciding if it is a metric. We also consider t…
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…
Lower Bounds for Convexity Testing
Xi Chen, Anindya De, Shivam Nadimpalli +2
We consider the problem of testing whether an unknown and arbitrary set (given as a black-box membership oracle) is convex, versus -far from…
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 (), and as a result, improve the best approximation for nearest nei…
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 and a dataset of points in a Euclidean space, and must prepare a data structure that can quickly…