11 papers
CALLIOPE: Private Insights into AI Use, Without Embeddings
Edith Cohen, Vadym Doroshenko, Badih Ghazi +11
We introduce CALLIOPE, a top-down framework for discovering topic hierarchies in large corpora of unstructured data (e.g., LLM conversations), while supporting differential privacy…
Tight Lower Bounds for Differentially Private Continual Counting
Charlie Harrison, Ethan Leeman
The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has remained unresolv…
Online Differentially Private Consistent Clustering
Edith Cohen, Vadym Doroshenko, Badih Ghazi +7
We study differentially private (DP) -means and -median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step, we need…
Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity
Matthew Regehr, Bingshan Hu, Ethan Leeman +3
We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We develop a general theory tha…
Nearly-Optimal Private Selection via Gaussian Mechanism
Ethan Leeman, Pasin Manurangsi
Steinke (2025) recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invok…
Andre-Quillen (co)homology and Equivariant Stable Homotopy Theory
Ethan Leeman
André and Quillen introduced a (co)homology theory for augmented commutative rings. Strickland initially proposed some issues with the analogue of the abelianization functor in the…
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-…
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…
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…
Affine extractors over large fields with exponential error
Jean Bourgain, Zeev Dvir, Ethan Leeman
We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem…