3 papers
cs.DS2025
Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model
Rachel Cummings, Alessandro Epasto, Jieming Mao +3
The turnstile continual release model of differential privacy captures scenarios where a privacy-preserving real-time analysis is sought for a dataset evolving through additions an…
cs.LG2024
Thompson Sampling Itself is Differentially Private
Tingting Ou, Marco Avella Medina, Rachel Cummings
In this work we first show that the classical Thompson sampling algorithm for multi-arm bandits is differentially private as-is, without any modification. We provide per-round priv…
cs.DS2022
Scheduling with Speed Predictions
Eric Balkanski, Tingting Ou, Clifford Stein +1
Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, ver…