15 papers
Differentially Private Substring and Document Counting with Near-Optimal Error
Giulia Bernardini, Philip Bille, Inge Li Gørtz +1
For databases consisting of many text documents, one of the most fundamental data analysis tasks is counting (i) how often a pattern appears as a substring in the database (substri…
Fully Dynamic Graph Algorithms with Edge Differential Privacy
Sofya Raskhodnikova, Teresa Anna Steiner
We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted ove…
Private Counting of Distinct Elements in the Turnstile Model and Extensions
Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner
Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023…
Count on Your Elders: Laplace vs Gaussian Noise
Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner +1
In recent years, Gaussian noise has become a popular tool in differentially private algorithms, often replacing Laplace noise which dominated the early literature. Gaussian noise i…
Continual Counting with Gradual Privacy Expiration
Joel Daniel Andersson, Monika Henzinger, Rasmus Pagh +2
Differential privacy with gradual expiration models the setting where data items arrive in a stream and at a given time the privacy loss guaranteed for a data item seen at time…
Private graph colouring with limited defectiveness
Aleksander B. G. Christiansen, Eva Rotenberg, Teresa Anna Steiner +1
Differential privacy is the gold standard in the problem of privacy preserving data analysis, which is crucial in a wide range of disciplines. Vertex colouring is one of the most f…