4 papers · 1 filter
Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries
Christian Janos Lebeda, Aleksandar Nikolov, Haohua Tang
We revisit the task of releasing marginal queries under differential privacy with additive (correlated) Gaussian noise. We first give a construction for answering arbitrary workloa…
Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch
Christian Janos Lebeda, Jakub TÄtek
We consider the problem of computing differentially private approximate histograms and heavy hitters in a stream of elements. In the non-private setting, this is often done using t…
The Correlated Gaussian Sparse Histogram Mechanism
Christian Janos Lebeda, Lukas Retschmeier
We consider the problem of releasing a sparse histogram under -differential privacy. The stability histogram independently adds noise from a Laplace or Gaussian…
Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space
Christian Janos Lebeda, Jakub TÄtek
Suppose we have a sample from a distribution and we want to test whether for a fixed distribution . Specifically, we want to reject with constant probability, if…