15 citations · 51 across the 40 of their papers we have counts for
5 papers · 1 filter
Optimal Algorithms for Augmented Testing of Discrete Distributions
Maryam Aliakbarpour, Piotr Indyk, Ronitt Rubinfeld +1
We consider the problem of hypothesis testing for discrete distributions. In the standard model, where we have sample access to an underlying distribution , extensive research h…
Statistical-Computational Trade-offs for Density Estimation
Anders Aamand, Alexandr Andoni, Justin Y. Chen +4
We study the density estimation problem defined as follows: given distributions over a discrete domain , as well as a collection of samples chosen from…
Differentially Private Gomory-Hu Trees
Anders Aamand, Justin Y. Chen, Mina Dalirrooyfard +4
Given an undirected, weighted -vertex graph , a Gomory-Hu tree is a weighted tree on such that for any pair of distinct vertices , the Min-…
A Bi-metric Framework for Fast Similarity Search
Haike Xu, Sandeep Silwal, Piotr Indyk
We propose a new "bi-metric" framework for designing nearest neighbor data structures. Our framework assumes two dissimilarity functions: a ground-truth metric that is accurate but…
Efficiently Computing Similarities to Private Datasets
Arturs Backurs, Zinan Lin, Sepideh Mahabadi +2
Many methods in differentially private model training rely on computing the similarity between a query point (such as public or synthetic data) and private data. We abstract out th…