39 citations · 308 across the 129 of their papers we have counts for
16 papers · 1 filter
Optimal Unbiased Randomizers for Regression with Label Differential Privacy
Ashwinkumar Badanidiyuru, Badih Ghazi, Pritish Kamath +5
We propose a new family of label randomizers for training regression models under the constraint of label differential privacy (DP). In particular, we leverage the trade-offs betwe…
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
Venkatesan Guruswami, Karthik C. S., Pasin Manurangsi +2
Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some such that given as input a -CSP inst…
Summary Reports Optimization in the Privacy Sandbox Attribution Reporting API
Hidayet Aksu, Badih Ghazi, Pritish Kamath +4
The Privacy Sandbox Attribution Reporting API has been recently deployed by Google Chrome to support the basic advertising functionality of attribution reporting (aka conversion me…
Sparsity-Preserving Differentially Private Training of Large Embedding Models
Badih Ghazi, Yangsibo Huang, Pritish Kamath +4
As the use of large embedding models in recommendation systems and language applications increases, concerns over user data privacy have also risen. DP-SGD, a training algorithm th…
User-Level Differential Privacy With Few Examples Per User
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
Previous work on user-level differential privacy (DP) [Ghazi et al. NeurIPS 2021, Bun et al. STOC 2023] obtained generic algorithms that work for various learning tasks. However, t…
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs
Euiwoong Lee, Pasin Manurangsi
We consider the question of approximating Max 2-CSP where each variable appears in at most constraints (but with possibly arbitrarily large alphabet). There is a simple $(\frac…
Differentially Private Aggregation via Imperfect Shuffling
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +2
In this paper, we introduce the imperfect shuffle differential privacy model, where messages sent from users are shuffled in an almost uniform manner before being observed by a cur…
Optimizing Hierarchical Queries for the Attribution Reporting API
Matthew Dawson, Badih Ghazi, Pritish Kamath +8
We study the task of performing hierarchical queries based on summary reports from the {\em Attribution Reporting API} for ad conversion measurement. We demonstrate that methods fr…
A Note on Hardness of Computing Recursive Teaching Dimension
Pasin Manurangsi
In this short note, we show that the problem of computing the recursive teaching dimension (RTD) for a concept class (given explicitly as input) requires -time, assu…
Ticketed Learning-Unlearning Schemes
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
We consider the learning--unlearning paradigm defined as follows. First given a dataset, the goal is to learn a good predictor, such as one minimizing a certain loss. Subsequently,…
Differentially Private Data Release over Multiple Tables
Badih Ghazi, Xiao Hu, Ravi Kumar +1
We study synthetic data release for answering multiple linear queries over a set of database tables in a differentially private way. Two special cases have been considered in the l…
On Differentially Private Sampling from Gaussian and Product Distributions
Badih Ghazi, Xiao Hu, Ravi Kumar +1
Given a dataset of i.i.d. samples from an unknown distribution , we consider the problem of generating a sample from a distribution that is close to in total variation d…
Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
We obtain a new protocol for binary counting in the -shuffle-DP model with error and expected communication $\tilde{O}\left(\frac{\log n}{\varepsilo…
On User-Level Private Convex Optimization
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
We introduce a new mechanism for stochastic convex optimization (SCO) with user-level differential privacy guarantees. The convergence rates of this mechanism are similar to those…
On Maximum Bipartite Matching with Separation
Pasin Manurangsi, Erel Segal-Halevi, Warut Suksompong
Maximum bipartite matching is a fundamental algorithmic problem which can be solved in polynomial time. We consider a natural variant in which there is a separation constraint: the…
Towards Separating Computational and Statistical Differential Privacy
Badih Ghazi, Rahul Ilango, Pritish Kamath +2
Computational differential privacy (CDP) is a natural relaxation of the standard notion of (statistical) differential privacy (SDP) proposed by Beimel, Nissim, and Omri (CRYPTO 200…