mlsanityData to 7 Oct 2026

Fixed-Parameter Tractability of Private Synthetic Data Generation

arXiv 2606.11283 ↗First posted 9 Jun 2026cs.DS cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

Builds on

20 of 55 references.

References · 20

  1. 2021Winning the NIST Contest: A scalable and general approach to differentially private synthetic datacited by 101
  2. 2022AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Datacited by 88
  3. 2019Graphical-model based estimation and inference for differential privacycited by 73
  4. 2020New Oracle-Efficient Algorithms for Private Synthetic Data Releasecited by 43
  5. 2022Geographic Spines in the 2020 Census Disclosure Avoidance Systemcited by 42
  6. 2019Practical Differentially Private Top-k Selection with Pay-what-you-get Compositioncited by 38
  7. 2014Dual Query: Practical Private Query Release for High Dimensional Datacited by 26
  8. 2022Private Online Prediction from Experts: Separations and Faster Ratescited by 17
  9. 2020A bounded-noise mechanism for differential privacycited by 15
  10. 2025How to DP-fy Your Data: A Practical Guide to Generating Synthetic Data With Differential Privacycited by 11
  11. 2021Privacy of synthetic data: a statistical frameworkcited by 10
  12. 2021A Single-Exponential Time 2-Approximation Algorithm for Treewidthcited by 8
8 more
  1. 2022Private Query Release via the Johnson-Lindenstrauss Transformcited by 8
  2. 2025Synthetic Tabular Data: Methods, Attacks and Defensescited by 8
  3. 2022On Differentially Private Counting on Treescited by 7
  4. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  5. 2020On Avoiding the Union Bound When Answering Multiple Differentially Private Queriescited by 5
  6. 2023Optimizing Hierarchical Queries for the Attribution Reporting APIcited by 3
  7. 2025Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queriescited by 3
  8. 2025PREM: Privately Answering Statistical Queries with Relative Errorcited by 2

Built on by

Not cited yet.