39 citations · 308 across the 129 of their papers we have counts for
22 papers · 1 filter
On the Differential Privacy and Interactivity of Privacy Sandbox Reports
Badih Ghazi, Charlie Harrison, Arpana Hosabettu +8
The Privacy Sandbox initiative from Google includes APIs for enabling privacy-preserving advertising functionalities as part of the effort around limiting third-party cookies. In p…
Balls-and-Bins Sampling for DP-SGD
Lynn Chua, Badih Ghazi, Charlie Harrison +6
We introduce the Balls-and-Bins sampling for differentially private (DP) optimization methods such as DP-SGD. While it has been common practice to use some form of shuffling in DP-…
How Unique is Whose Web Browser? The role of demographics in browser fingerprinting among US users
Alex Berke, Enrico Bacis, Badih Ghazi +5
Browser fingerprinting can be used to identify and track users across the Web, even without cookies, by collecting attributes from users' devices to create unique "fingerprints". T…
Scalable DP-SGD: Shuffling vs. Poisson Subsampling
Lynn Chua, Badih Ghazi, Pritish Kamath +4
We provide new lower bounds on the privacy guarantee of the multi-epoch Adaptive Batch Linear Queries (ABLQ) mechanism with shuffled batch sampling, demonstrating substantial gaps…
Differential Privacy on Trust Graphs
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
We study differential privacy (DP) in a multi-party setting where each party only trusts a (known) subset of the other parties with its data. Specifically, given a trust graph wher…
Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy
Yangsibo Huang, Daogao Liu, Lynn Chua +7
Machine unlearning algorithms, designed for selective removal of training data from models, have emerged as a promising approach to growing privacy concerns. In this work, we expos…
Perfect sampling from rapidly mixing Markov chains
Andreas Göbel, Jingcheng Liu, Pasin Manurangsi +1
We show that efficient approximate sampling algorithms, combined with a slow exponential time oracle for computing its output distribution, can be combined into constructing effici…
Fine Grained Lower Bounds for Multidimensional Knapsack
Ilan Doron-Arad, Ariel Kulik, Pasin Manurangsi
We study the -dimensional knapsack problem. We are given a set of items, each with a -dimensional cost vector and a profit, along with a -dimensional budget vector. The go…
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on variables and alphab…
On Convex Optimization with Semi-Sensitive Features
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
We study the differentially private (DP) empirical risk minimization (ERM) problem under the semi-sensitive DP setting where only some features are sensitive. This generalizes the…
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…
Crosslingual Capabilities and Knowledge Barriers in Multilingual Large Language Models
Lynn Chua, Badih Ghazi, Yangsibo Huang +6
Large language models (LLMs) are typically multilingual due to pretraining on diverse multilingual corpora. But can these models relate corresponding concepts across languages, i.e…
Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning
Lynn Chua, Badih Ghazi, Yangsibo Huang +6
Large language models (LLMs) have emerged as powerful tools for tackling complex tasks across diverse domains, but they also raise privacy concerns when fine-tuned on sensitive dat…
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…
Complexity of Round-Robin Allocation with Potentially Noisy Queries
Zihan Li, Pasin Manurangsi, Jonathan Scarlett +1
We study the complexity of a fundamental algorithm for fairly allocating indivisible items, the round-robin algorithm. For agents and items, we show that the algorithm can…
Ordinal Maximin Guarantees for Group Fair Division
Pasin Manurangsi, Warut Suksompong
We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial mult…
Differentially Private Optimization with Sparse Gradients
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +2
Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optim…
Differentially Private Ad Conversion Measurement
John Delaney, Badih Ghazi, Charlie Harrison +6
In this work, we study ad conversion measurement, a central functionality in digital advertising, where an advertiser seeks to estimate advertiser website (or mobile app) conversio…
Improved Lower Bound for Differentially Private Facility Location
Pasin Manurangsi
We consider the differentially private (DP) facility location problem in the so called super-set output setting proposed by Gupta et al. [SODA 2010]. The current best known expecte…
How Private are DP-SGD Implementations?
Lynn Chua, Badih Ghazi, Pritish Kamath +4
We demonstrate a substantial gap between the privacy guarantees of the Adaptive Batch Linear Queries (ABLQ) mechanism under different types of batch sampling: (i) Shuffling, and (i…
Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
Pasin Manurangsi
In the Max -Weight SAT (aka Max SAT with Cardinality Constraint) problem, we are given a CNF formula with variables and clauses together with a positive integer . The…
Training Differentially Private Ad Prediction Models with Semi-Sensitive Features
Lynn Chua, Qiliang Cui, Badih Ghazi +9
Motivated by problems arising in digital advertising, we introduce the task of training differentially private (DP) machine learning models with semi-sensitive features. In this se…