7 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}…
On the Parameterized Complexity of Semitotal Domination on Graph Classes
Lukas Retschmeier
For a given graph , a subset of the vertices is called a semitotal dominating set, if is a dominating set and every vertex is within distan…
Revisiting a Successful Reduction Rule for Dominating Set
Lukas Geis, Alexander Leonhardt, Johannes Meintrup +3
Given a graph with vertices and edges, the DominatingSet problem asks for a set of minimal cardinality such that every vertex either is in …
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…
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…
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 …
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…