65 citations · 177 across the 68 of their papers we have counts for
7 papers · 1 filter
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
In this work, we study the problem of answering queries with -differential privacy, where each query has sensitivity one. We give an algorithm for this task that achiev…
Sample-efficient proper PAC learning with approximate differential privacy
Badih Ghazi, Noah Golowich, Ravi Kumar +1
In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension with approximate differential privacy is , ignoring priva…
Robust and Private Learning of Halfspaces
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
In this work, we study the trade-off between differential privacy and adversarial robustness under L2-perturbations in the context of learning halfspaces. We prove nearly tight bou…
On Distributed Differential Privacy and Counting Distinct Elements
Lijie Chen, Badih Ghazi, Ravi Kumar +1
We study the setup where each of users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of…
Differentially Private Clustering: Tight Approximation Ratios
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient…
Near-tight closure bounds for Littlestone and threshold dimensions
Badih Ghazi, Noah Golowich, Ravi Kumar +1
We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes of Boolean functions wit…
Pure Differentially Private Summation from Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar +3
The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but…