# Fixed-Parameter Tractability of Private Synthetic Data Generation

arXiv: https://arxiv.org/abs/2606.11283 · HTML: https://mlsanity.com/paper/2606.11283/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 55 references that are in the map.
- First posted on arXiv 9 Jun 2026.

## Builds on (most cited first, 20 of 20)

- [Winning the NIST Contest: A scalable and general approach to differentially private synthetic data](https://mlsanity.com/paper/2108.04978/) (2021)
- [AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data](https://mlsanity.com/paper/2201.12677/) (2022)
- [Graphical-model based estimation and inference for differential privacy](https://mlsanity.com/paper/1901.09136/) (2019)
- [Geographic Spines in the 2020 Census Disclosure Avoidance System](https://mlsanity.com/paper/2203.16654/) (2022)
- [New Oracle-Efficient Algorithms for Private Synthetic Data Release](https://mlsanity.com/paper/2007.05453/) (2020)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Dual Query: Practical Private Query Release for High Dimensional Data](https://mlsanity.com/paper/1402.1526/) (2014)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [A bounded-noise mechanism for differential privacy](https://mlsanity.com/paper/2012.03817/) (2020)
- [How to DP-fy Your Data: A Practical Guide to Generating Synthetic Data With Differential Privacy](https://mlsanity.com/paper/2512.03238/) (2025)
- [Privacy of synthetic data: a statistical framework](https://mlsanity.com/paper/2109.01748/) (2021)
- [Synthetic Tabular Data: Methods, Attacks and Defenses](https://mlsanity.com/paper/2506.06108/) (2025)
- [A Single-Exponential Time 2-Approximation Algorithm for Treewidth](https://mlsanity.com/paper/2104.07463/) (2021)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [On Differentially Private Counting on Trees](https://mlsanity.com/paper/2212.11967/) (2022)
- [Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems](https://mlsanity.com/paper/2403.02912/) (2024)
- [On Avoiding the Union Bound When Answering Multiple Differentially Private Queries](https://mlsanity.com/paper/2012.09116/) (2020)
- [Optimizing Hierarchical Queries for the Attribution Reporting API](https://mlsanity.com/paper/2308.13510/) (2023)
- [Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries](https://mlsanity.com/paper/2512.21499/) (2025)
- [PREM: Privately Answering Statistical Queries with Relative Error](https://mlsanity.com/paper/2502.14809/) (2025)

## Abstract (arXiv)

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.