34 citations · 80 across the 12 of their papers we have counts for
8 papers · 1 filter
Uniformity Testing under User-Level Local Privacy
Clément L. Canonne, Abigail Gentle, Vikrant Singhal
We initiate the study of distribution testing under \emph{user-level} local differential privacy, where each of users contributes samples from the unknown underlying distri…
Not All Learnable Distribution Classes are Privately Learnable
Mark Bun, Gautam Kamath, Argyris Mouzakis +1
We give an example of a class of distributions that is learnable up to constant error in total variation distance with a finite number of samples, but not learnable under $(\vareps…
A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
Vikrant Singhal
We present the first -differentially private, computationally efficient algorithm that estimates the means of product distributions over accurately in tota…
New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
Gautam Kamath, Argyris Mouzakis, Vikrant Singhal
We prove new lower bounds for statistical estimation tasks under the constraint of -differential privacy. First, we provide tight lower bounds for private covaria…
Private Mean Estimation of Heavy-Tailed Distributions
Gautam Kamath, Vikrant Singhal, Jonathan Ullman
We give new upper and lower bounds on the minimax sample complexity of differentially private mean estimation of distributions with bounded -th moments. Roughly speaking, in the…
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians
Gautam Kamath, Or Sheffet, Vikrant Singhal +1
Learning the parameters of Gaussian mixture models is a fundamental and widely studied problem with numerous applications. In this work, we give new algorithms for learning the par…
Privately Learning High-Dimensional Distributions
Gautam Kamath, Jerry Li, Vikrant Singhal +1
We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian and lear…
Deterministic and Probabilistic Binary Search in Graphs
Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal
We consider the following natural generalization of Binary Search: in a given undirected, positively weighted graph, one vertex is a target. The algorithm's task is to identify the…