Fixed-Parameter Tractability of Private Synthetic Data Generation

Badih Ghazi; Cristóbal Guzmán; Pritish Kamath; Alexander Knop; Ravi Kumar; Pasin Manurangsi

cs.DSJun 9, 2026

Fixed-Parameter Tractability of Private Synthetic Data Generation

Authors: Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi

Organizations: Google Deepmind · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Cat´olica de Chile · Google Research

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.

Explore similar work

Differentially Private Synthetic Data via APIs 4: Tabular Data
Jun 6, 2026Toan Tran, Arturs Backurs, Zinan Lin +3Synthetic Tabular Data Differential Privacy
Tight Auditing of Differential Privacy in MST and AIM
Apr 20, 2026Georgi Ganev, Meenatchi Sundaram Muthu Selva Annamalai, Bogdan KulynychDifferential Privacy AI Privacy Risks and Protection
Private Seeds, Public LLMs: Realistic and Privacy-Preserving Synthetic Data Generation
Apr 8, 2026Qian Ma, Sarah RajtmajerSynthetic Data Differential Privacy

Jun 6, 2026 · cs.LGJ/K move · Enter open · S save

Differentially Private Synthetic Data via APIs 4: Tabular Data

Toan Tran, Arturs Backurs, Zinan Lin, Victor Reis+2

This paper investigates the problem of generating synthetic tabular data with differential privacy (DP) guarantees, enabling data sharing in sensitive domains. Despite extensive study, state-of-the-art methods often focus on minimizing low-order marginal query errors and overlook the challenges posed by high-order correlations. To address this gap, we extend the Private Evolution (PE) framework, originally developed for DP-compliant image and text synthesis, to tabular data. We introduce Tab-PE -- an algorithm for synthetic tabular data generation under DP constraints. Tab-PE iteratively improves a candidate dataset via an evolutionary process that leverages tabular-specialized operators to produce variations, privately scores them, and selects the highest-quality samples to retain and propagate. In contrast to the original PE, which relies on large foundation models, Tab-PE employs heuristic operators with significantly lower computational costs, making PE more practical and scalable for tabular data. Through extensive experiments on real-world and simulation datasets, we demonstrate that Tab-PE substantially outperforms prior baselines on datasets exhibiting high-order correlations. Compared to the best baseline -- AIM, Tab-PE improves classification accuracy by up to 10% while running 28 times faster.

Synthetic Tabular Data Differential Privacy Synthetic Data Tabular Data Alphaevolve Higher-Order Correlations Application Programming Interfaces

Open paper Ask about it PDF

Abstract

Explore similar work

Differentially Private Synthetic Data via APIs 4: Tabular Data

Tight Auditing of Differential Privacy in MST and AIM

Private Seeds, Public LLMs: Realistic and Privacy-Preserving Synthetic Data Generation