Showing 2024Show all
3 papers · 1 filter
cs.DS2024
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 d…
cs.DS2024
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 …
cs.DS2024
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…