39 citations · 308 across the 129 of their papers we have counts for
16 papers · 1 filter
On Differentially Private Counting on Trees
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
We study the problem of performing counting queries at different levels in hierarchical structures while preserving individuals' privacy. Motivated by applications, we propose a ne…
Regression with Label Differential Privacy
Badih Ghazi, Pritish Kamath, Ravi Kumar +4
We study the task of training regression models with the guarantee of label differential privacy (DP). Based on a global prior distribution on label values, which could be obtained…
Differentially Private Heatmaps
Badih Ghazi, Junfeng He, Kai Kohlhoff +4
We consider the task of producing heatmaps from users' aggregated data while protecting their privacy. We give a differentially private (DP) algorithm for this task and demonstrate…
Differentially Private Fair Division
Pasin Manurangsi, Warut Suksompong
Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources us…
Private Counting of Distinct and k-Occurring Items in Time Windows
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
In this work, we study the task of estimating the numbers of distinct and -occurring items in a time window under the constraint of differential privacy (DP). We consider severa…
Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique
Pasin Manurangsi
We study the complexity of computing (and approximating) VC Dimension and Littlestone's Dimension when we are given the concept class explicitly. We give a simple reduction from Ma…
Private Ad Modeling with DP-SGD
Carson Denison, Badih Ghazi, Pritish Kamath +6
A well-known algorithm in privacy-preserving ML is differentially private stochastic gradient descent (DP-SGD). While this algorithm has been evaluated on text and image data, it h…
Anonymized Histograms in Intermediate Privacy Models
Badih Ghazi, Pritish Kamath, Ravi Kumar +1
We study the problem of privately computing the anonymized histogram (a.k.a. unattributed histogram), which is defined as the histogram without item labels. Previous works have pro…
Private Isotonic Regression
Badih Ghazi, Pritish Kamath, Ravi Kumar +1
In this paper, we consider the problem of differentially private (DP) algorithms for isotonic regression. For the most general problem of isotonic regression over a partially order…
Algorithms with More Granular Differential Privacy Guarantees
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
Differential privacy is often applied with a privacy parameter that is larger than the theory suggests is ideal; various informal justifications for tolerating large privacy parame…
Cryptographic Hardness of Learning Halfspaces with Massart Noise
Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi +1
We study the complexity of PAC learning halfspaces in the presence of Massart noise. In this problem, we are given i.i.d. labeled examples $(\mathbf{x}, y) \in \mathbb{R}^N \times…
Faster Privacy Accounting via Evolving Discretization
Badih Ghazi, Pritish Kamath, Ravi Kumar +1
We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for composition of mechanisms.…
Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions
Vadym Doroshenko, Badih Ghazi, Pritish Kamath +2
The privacy loss distribution (PLD) provides a tight characterization of the privacy loss of a mechanism in the context of differential privacy (DP). Recent work has shown that PLD…
Fixing Knockout Tournaments With Seeds
Pasin Manurangsi, Warut Suksompong
Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by…
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
We study the problem of releasing the weights of all-pair shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fix…
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee +1
We study several questions related to diversifying search results. We give improved approximation algorithms in each of the following problems, together with some lower bounds. - W…