From the 1 of 26 linked papers with an AI index.
4 papers · 1 filter
Fixed-Parameter Tractability of Private Synthetic Data Generation
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3
The paper investigates generating differentially private synthetic data and shows that the problem is fixed-parameter tractable when parameterized by the treewidth of the query fam…
Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
Lynn Chua, Badih Ghazi, Ravi Kumar +3
We study the problem of Stochastic Convex Optimization (SCO) under the constraint of local Label Differential Privacy (L-LDP). In this setting, the features are considered public,…
On Computing Pairwise Statistics with Local Differential Privacy
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
We study the problem of computing pairwise statistics, i.e., ones of the form , where denotes the input to the th user, with…
Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation: if an algorithm is one-sided add-DP, then its subsampled…