Fixed-Parameter Tractability of Private Synthetic Data Generation

Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3

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…