Fixed-Parameter Tractability of Private Synthetic Data Generation
arXiv:2606.11283v2 proves that synthetic data generation under differential privacy is fixed-parameter tractable (FPT) parameterized by the treewidth of the query family’s incidence graph; both proposed algorithms achieve optimal error rates across all regimes and are unified by a dynamic programming framework over a tree decomposition.
Core Result
The problem of synthetic data generation under differential privacy is rigorously shown to be fixed-parameter tractable (FPT), with the treewidth of the query family’s incidence graph as the parameter—a structural measure capturing sparsity in query dependencies.
Algorithmic Design and Theoretical Contribution
- FPT via LP dual separation: Formulates synthetic data generation as a linear program (LP); the separation problem for its dual is solved in FPT time w.r.t. treewidth, yielding an overall FPT algorithm;
- Subsampled private multiplicative weights: Extends the classic Multiplicative Weights Mechanism, where sampling from the Gibbs distribution is proven FPT when parameterized by treewidth;
- Unified framework: Both approaches rely on dynamic programming over a tree decomposition of the incidence graph, highlighting how structural priors fundamentally enable efficient private computation.
Practical Implication
This work provides the first theoretically grounded path toward efficient private synthesis for high-dimensional, structured queries (e.g., join-heavy SQL workloads or graph pattern queries), circumventing exponential blowup inherent in generic mechanisms; treewidth—being computable in practice—also enables automated identification of ‘tractable’ query subsets in deployed systems.