Fixed-Parameter Tractability of Private Synthetic Data Generation
arXiv:2606.11283
The paper investigates generating differentially private synthetic data and shows that the problem is fixed-parameter tractable when parameterized by the treewidth of the query family's incidence graph, achieving optimal error rates via linear programming and private multiplicative weights methods.
Abstract
We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth of the query family's incidence graph. Our algorithms attain optimal error rates across all regimes and are realized by two different approaches: the first is based on linear programming (LP) and the FPT of the separation problem for the LP dual; the second is based on a subsampled private multiplicative weights method, where we obtain FPT for sampling from Gibbs distributions. Both approaches are unified by a dynamic programming framework over a tree decomposition.
Fixed typos. Included new results on tighter error rates for bounded treewidth families (now in Section 5)