1 citations · 1 across the 10 of their papers we have counts for
15 papers
Lower Bounds for Private Graph Optimization Problems using Reconstruction Attacks
Jacob Imola, Rasmus Pagh, Lukas Retschmeier
This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w}…
Dithered Gaussian Mechanism for Randomness-Efficient Differential Privacy
Nikita P. Kalinin, Rasmus Pagh
We present the dithered Gaussian mechanism, an alternative to the discrete Gaussian mechanism for differential privacy that discretizes the private output rather than the noise dis…
Privacy by Postprocessing the Discrete Laplace Mechanism
Quentin Hillebrand, Jacob Imola, Rasmus Pagh +1
We show that an "old dog", the classical discrete Laplace (aka.~geometric) mechanism, can "perform new tricks": 1. It can be post-processed to yield a simple, unbiased estimator of…
DP-λCGD: Efficient Noise Correlation for Differentially Private Model Training
Nikita P. Kalinin, Ryan McKenna, Rasmus Pagh +1
Differentially private stochastic gradient descent (DP-SGD) is the gold standard for training machine learning models with formal differential privacy guarantees. Several recent ex…
Piquant: Private Quantile Estimation in the Two-Server Model
Hannah Keller, Jacob Imola, Fabrizio Boninsegna +2
Quantiles are key in distributed analytics, but computing them over sensitive data risks privacy. Local differential privacy (LDP) offers strong protection but lower accuracy than…
Private Lossless Multiple Release
Joel Daniel Andersson, Lukas Retschmeier, Boel Nelson +1
Koufogiannis et al. (2016) showed a result for Laplace noise-based differentially private mechanisms: given an -DP release, a new release wi…
Differentially Private Quantiles with Smaller Error
Jacob Imola, Fabrizio Boninsegna, Hannah Keller +3
In the approximate quantiles problem, the goal is to output quantile estimates, the ranks of which are as close as possible to given quantiles $0 \leq q_1 \leq\dots \leq q_…
Lightweight Protocols for Distributed Private Quantile Estimation
Anders Aamand, Fabrizio Boninsegna, Abigail Gentle +2
Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We co…
Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation
Rasmus Pagh, Lukas Retschmeier, Hao Wu +1
We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph where is a set of vertices, is a set of …
Streaming Private Continual Counting via Binning
Joel Daniel Andersson, Rasmus Pagh
In differential privacy, refers to problems in which we wish to continuously release a function of a dataset that is revealed one element at a time…
Faster Private Minimum Spanning Trees
Rasmus Pagh, Lukas Retschmeier
Motivated by applications in clustering and synthetic data generation, we consider the problem of releasing a minimum spanning tree (MST) under edge-weight differential privacy con…
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…
Profile Reconstruction from Private Sketches
Hao Wu, Rasmus Pagh
Given a multiset of items from , the \emph{profile reconstruction} problem is to estimate, for , the fraction of items in $\mathca…
Aleph Filter: To Infinity in Constant Time
Niv Dayan, Ioana-Oriana Bercea, Rasmus Pagh
Filter data structures are widely used in various areas of computer science to answer approximate set-membership queries. In many applications, the data grows dynamically, requirin…