Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Private synthetic data generation is fixed-parameter tractable in the treewidth of the query family's incidence graph, achieving optimal error rates in all regimes.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 11:50 UTC pith:H5FBZP3Q

load-bearing objection The central DP is broken: Lemma 31 is false and an AND query already makes the algorithm overcount; the FPT results are unsupported as written. the 2 major comments →

arxiv 2606.11283 v2 pith:H5FBZP3Q submitted 2026-06-09 cs.DS cs.LGstat.ML

Fixed-Parameter Tractability of Private Synthetic Data Generation

Badih Ghazi , Crist\'obal Guzm\'an , Pritish Kamath , Alexander Knop , Ravi Kumar , Pasin Manurangsi This is my paper
classification cs.DS cs.LGstat.ML
keywords differential privacysynthetic datafixed-parameter tractabilitytreewidthincidence graphmultiplicative weightsGibbs samplinglinear programming dual
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Private synthetic data generation asks for a new dataset that answers a given family of counting queries almost as well as the sensitive original while satisfying differential privacy. This paper shows the problem is fixed-parameter tractable in the treewidth of the query family's incidence graph: the exponential dependence moves from the domain dimension d to a width parameter w, so instances with structured query overlap become tractable even when the domain is huge. Concretely, it gives two algorithms — one through the dual of a linear program and the separation problem, one through subsampled private multiplicative weights and perfect Gibbs sampling — that both run in poly(d, |F|, n, 2^w, size(F)) and match the known optimal error rates in the small-family and sparse-data regimes, and the best known pure-DP bound. A single dynamic program over a tree decomposition underlies both, evaluating optimization and partition-function objectives over the Boolean hypercube. If correct, this unifies previously ad hoc tractable cases such as hierarchical, partitioned-marginal, tree-structured, and low-dimensional spatial query families.

Core claim

On the paper's own terms, the central discovery is a fixed-parameter algorithm: for any Boolean query family F represented by rOBDDs, the difficulty of private synthetic data generation is governed by the treewidth w of the bipartite incidence graph between variables and queries. Given a nice tree decomposition of width w, one dynamic program computes both the maximum of sum over f of y_f f(x) over x — the separation oracle for the dual LP, used in the small-family regime — and the partition function of the Gibbs distribution with weights sum over f of z_f f(x), used by the implicit private multiplicative weights algorithm in the sparse regime. Because only states over bags are stored, runti

What carries the argument

The machine is a nice tree decomposition of the bipartite incidence graph G(F) whose vertices are variables and queries, with width w = tw(F). At each bag, a state consists of assignments to variables and to query values; a query value is consistent only if it is a possible residual given the partial variable assignment, and Lemma 31 says residuals can be determined using only downward information because any scope variable appearing outside the processed subtree must be in the current bag. The dynamic program evaluates either max-plus or sum-product objectives in one template, producing the maximum of sum_f y_f f(x) needed by the LP separation oracle and the partition function Z(beta) neede

Load-bearing premise

The whole dynamic programming machinery rests on the claim that whenever a query function sits in a current bag, every variable it depends on that appears anywhere in the already-processed part of the tree must also be in that bag; if this separator property fails, the residual consistency oracle and both algorithms break.

What would settle it

Run the dynamic program on a small family (say d = 8, |F| = 10) with a tree decomposition where a query's scope variable is forgotten in a child subtree but absent from the parent bag, and compare the DP's computed optimum and partition function against brute-force enumeration over all 2^d assignments. Any mismatch would refute the consistency lemma and hence the correctness theorems; a mismatch-free random-instance comparison would support the central claim.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Hierarchical or laminar query families of depth h can be answered in time poly(n, d, 2^h) with error O(h ln|F| / (n epsilon)) for pure DP and O(sqrt(h ln|F| ln(1/delta)) / (n epsilon)) for approximate DP.
  • Partitioned k-way marginal queries are handled in poly(d, n, 2^k) time, and the sparse-regime algorithm can beat the dense LP route under an explicit condition on n, epsilon, delta, d, and k.
  • Any query family whose incidence graph has constant treewidth, such as tree-structured Markov random field marginals, yields polynomial-time DP synthetic data generation.
  • Because the slow term is 2^w rather than 2^d, structured workloads such as hierarchical queries evade the general exponential-in-d hardness without restricting to parametric distribution families.
  • The reduction is modular: any DP mechanism that answers a query family with accuracy alpha automatically upgrades to a DP synthetic data generator with O(alpha) error plus the FPT overhead.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • (Editorial inference) The semiring abstraction implies the tree-decomposition dynamic program is a general engine for optimization and counting with low-treewidth Boolean function families, so it should transfer beyond synthetic data to tasks like private empirical risk minimization with structured losses.
  • (Editorial inference) Because the reduction is modular, future improvements to DP query answering — including a settled optimal pure-DP rate — can be plugged in directly to improve the synthetic-data error without reworking the treewidth machinery.
  • (Editorial inference) A natural next experiment is to instantiate both algorithms on large low-treewidth workloads — hierarchical, grid, tree-structured marginals — and compare the Gibbs sampler's empirical error and running time against existing workload-adaptive mechanisms; the paper stops at worst-case guarantees.
  • (Editorial inference) If Lemma 31 were ever found to fail for a non-standard tree decomposition, the DP could likely be repaired by augmenting bags with boundary variables, trading a larger width for correctness; this repair is not explored in the paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes fixed-parameter tractable algorithms for differentially private synthetic data generation, parameterized by the treewidth of the incidence graph of the query family. Two mechanisms are presented: one based on solving the dual of a natural LP via the ellipsoid method with an FPT separation oracle, and one based on a subsampled private multiplicative-weights method whose Gibbs-sampling step is implemented by a tree-decomposition dynamic program. The paper claims optimal error rates in the small-query-family regime and in the sparse-data regime, with running time poly(d, |F|, n, 2^{tw(F)}, size(F)). The results are unified through a semiring DP (dynamic program) over a nice tree decomposition of the incidence graph, and several applications are given, including hierarchical queries, partitioned marginals, Chow--Liu trees, and spatial families.

Significance. If correct, the claimed results would be significant: they would give a broad structural parameterization under which worst-case-optimal DP synthetic data generation becomes fixed-parameter tractable, unifying and extending known tractable cases such as hierarchical queries and low-treewidth graphical-model workloads. The semiring framework for jointly treating optimization and partition-function evaluation is elegant, and the rOBDD representation is a sensible input model. The algorithmic ideas are clearly presented and the applications are well chosen. However, the central correctness argument rests on a false structural lemma, and a simple treewidth-1 example invalidates the DP, the LP separation oracle, and the Gibbs sampler. Thus the main contribution is not supported as written.

major comments (2)
  1. [A.3, Lemmas 30/31; Cor. 15, Prop. 18, Thm. 19] Lemma 30 is false as stated. The standard separator lemma says that X_a∩X_b separates A\B from B\A; it does not imply ∂(A),∂(B)⊆X_a∩X_b. Counterexample to Lemma 31: F={f}, f(x)=x1 AND x2, with the valid width-1 nice path decomposition ∅,{f},{f,x1},{f},{f,x2},{f},∅. At the node t with bag {f} immediately after forgetting x1, the outside part B contains x2∈scope[f], yet x2∉X_t. The DP then overcounts: for the sum-product semiring it returns 4·ψ(0)+1·ψ(1), whereas the true partition function is 3·ψ(0)+1·ψ(1), because the state u_f=0 at t aggregates forgotten assignments to x1 that are incompatible with some later partial assignment to x2. Since Corollary 15, Proposition 18, Theorem 19, and consequently the LP separation oracle in (1) and the Gibbs sampler in Section 6 all depend on Lemma 31, the central FPT claim is not established. The failure occurs at treewidth 1, so it is not a boundary
  2. [Theorem 11 and Algorithm 1 (Section 4)] Theorem 11 is stated for 'appropriate values of τ, m, η', but the proof fixes τ and m while never instantiating η. In Algorithm 1, η is the Gibbs temperature passed to Sample(z,η), and it is load-bearing for the multiplicative-weights update: the proof invokes a standard MWU analysis without specifying how η relates to T, τ, or the accuracy bound. Without a concrete step size, the claimed running time and accuracy cannot be verified from the text, and the algorithm as written is not fully specified.
minor comments (4)
  1. [Throughout] Algorithm 1 is used both for IPMWU (Section 4) and for the value-function dynamic program (Section 5); Section 6's sampler is Algorithm 2. This makes references such as 'Algorithm 1 contains a detailed description' ambiguous. Please renumber.
  2. [Section 3, (D)] The dual LP is said to have '2^d constraints' but the text says '2d constraints'; the dual has one constraint per x∈{0,1}^d.
  3. [Section 5, Definition 16] The notation f(y) for y∈{0,1}^{I^↓_t} is only meaningful when scope[f]⊆I^↓_t. The paper's justification is deferred to Lemma 31; once Lemma 31 is repaired or replaced, this step needs an explicit proof.
  4. [Theorem 11 proof] The proof says 'all queries (hat f_t) have margin τ/3 at each iteration' after a FAIL event, but the algorithm only directly bounds the chosen query's margin. The standard MWU argument should be written out so that the implication is transparent.

Circularity Check

0 steps flagged

No significant circularity: the FPT results are derived from structural arguments, not from fitted targets or self-citation chains.

full rationale

The paper's central derivation is self-contained against the claimed benchmarks. The optimal rates cited in the introduction are external lower/upper bounds (Vadhan 2017; Hardt-Rothblum 2010; Ghazi et al. 2021; Dagan-Kur 2022), and the algorithms' error claims are not fitted parameters: τ, m, η in Theorem 11 are chosen by closed-form expressions, and the LP/PMWU reductions follow the standard duality and multiplicative-weights arguments rather than assuming the conclusion. The DP recurrence (Proposition 18) and the consistency/oracle definitions (Definition 14, Corollary 15) are defined in terms of scope and the tree decomposition, not in terms of the target error rates; no step of the form 'X is fitted from the quantity that X is then said to predict' appears. Self-citations (e.g., Ghazi et al. 2025 for MWU analysis, Ghazi et al. 2021 for query mechanisms) are used as independent prior results or as pointers to standard analysis, and the main FPT argument does not reduce to them. The appended skeptical objection about Lemma 31, even if substantively correct, would be a technical correctness flaw in the dynamic program, not a circularity: it does not show that a claimed prediction equals its input by construction. Accordingly, there is no circular step to flag.

Axiom & Free-Parameter Ledger

3 free parameters · 7 axioms · 0 invented entities

No new physical or mathematical entities are postulated. The mechanism parameters eta, C, tau, and m are algorithm hyperparameters rather than fitted constants, though several are left unspecified. All background relies on standard DP, LP, treewidth, and semiring techniques.

free parameters (3)
  • eta (MWU step size)
    Algorithm 1 and Theorem 12 state 'for appropriate values of eta', but no value or range is ever specified. The proof of Theorem 11 does not instantiate it.
  • C (constant in threshold tau)
    Theorem 11 sets tau = C * (rate expression) with C 'sufficiently large'. Existence of such a constant is asserted to make union bounds hold, but not quantified.
  • threshold tau and sample size m
    tau and m are set as functions of d, n, epsilon, |F| in Theorem 11, not fitted to data. They are algorithm hyperparameters needed for the accuracy guarantee.
axioms (7)
  • standard math LP duality and complementary slackness produce a primal optimal solution with small support
    Used in Section 3, Theorem 7, to go from an optimal dual solution to a sparse fractional histogram.
  • standard math Ellipsoid method with a polynomial-time separation oracle solves the dual LP
    Used in Lemma 6; the separation oracle is max_x sum_f y_f f(x) <= 0.
  • standard math Standard multiplicative-weights convergence analysis
    Used in Theorem 11; the paper cites Mohri et al. and its own Ghazi et al. 2025 Claim 3.3.
  • standard math Differential privacy composition theorems and Laplace/exponential mechanism guarantees
    Used throughout, formally stated in Appendix A.1.
  • standard math Tree decompositions can be approximated and converted to nice tree decompositions in FPT time
    Invoked in Section 5, citing Korhonen 2021 and Cygan et al. Lemma 7.4.
  • domain assumption Query functions are represented as rOBDDs and scope[f] is exactly the set of variables appearing in the rOBDD
    Assumed in Section 2; Lemma 3 asserts it. This representation is the input model for all algorithms.
  • domain assumption The incidence graph treewidth of the query family is a meaningful parameter for the workload
    The paper's entire FPT claim is conditioned on the query family admitting a bounded-treewidth incidence graph.

pith-pipeline@v1.3.0-alltime-deepseek · 19492 in / 15029 out tokens · 172099 ms · 2026-08-02T11:50:10.059784+00:00 · methodology

0 comments
read the original 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.

Figures

Figures reproduced from arXiv: 2606.11283 by Alexander Knop, Badih Ghazi, Crist\'obal Guzm\'an, Pasin Manurangsi, Pritish Kamath, Ravi Kumar.

Figure 1
Figure 1. Figure 1: Reduced Ordered Binary Decision Diagram (rOBDD) for the 3-variable Majority function [PITH_FULL_IMAGE:figures/full_fig_p022_1.png] view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

    cs.DS 2026-07 accept novelty 8.0 full

    For any finite query set and data universe, a pure ε-DP mechanism releases all k query answers with expected worst-coordinate error O(min{1, sqrt(log(2T) log(2k) / (εn))}), matching known lower bounds.

  2. Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

    cs.DS 2026-07 conditional novelty 7.0

    Under pure differential privacy, k statistical queries over a universe of size T can be answered with expected worst-coordinate error O(min{1, sqrt(log(2T)log(2k)/(εn))}), matching known lower bounds.

Reference graph

Works this paper leans on

54 extracted references · 1 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Abowd, R

    J. Abowd, R. Ashmead, G. Simson, D. Kifer, P. Leclerc, A. Machanavajjhala, and W. Sexton. Census TopDown : Differentially private data, incremental schemas, and consistency with public knowledge. US Census Bureau, pages 1--21, 2019

    2019

  2. [2]

    J. M. Abowd. The U.S. Census Bureau adopts differential privacy. In KDD, page 2867, 2018

    2018

  3. [3]

    J. M. Abowd, R. Ashmead, R. Cumings-Menon, S. Garfinkel, M. Heineck, C. Heiss, R. Johns, D. Kifer, P. Leclerc, A. Machanavajjhala, B. Moran, W. Sexton, M. Spence, and P. Zhuravlev. The 2020 Census Disclosure Avoidance System TopDown Algorithm . Harvard Data Science Review, Special Issue 0 (2), 2022

    2020

  4. [4]

    Arora, E

    S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8 0 (1): 0 121--164, 2012

    2012

  5. [5]

    H. Asi, V. Feldman, T. Koren, and K. Talwar. Private online prediction from experts: Separations and faster rates. In COLT, pages 674--699, 2023

    2023

  6. [6]

    B. S. Baker. Approximation algorithms for NP -complete problems on planar graphs. J. ACM , 41 0 (1): 0 153--180, 1994

    1994

  7. [7]

    Barak, K

    B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In PODS, pages 273--282, 2007

    2007

  8. [8]

    Bez \'a kov \'a , E

    I. Bez \'a kov \'a , E. W. Chambers, and K. Fox. Integrating and sampling cuts in bounded treewidth graphs. In AWM, pages 401--415, 2016

    2016

  9. [9]

    A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. In STOC, pages 609--618, 2008

    2008

  10. [10]

    Boedihardjo, T

    M. Boedihardjo, T. Strohmer, and R. Vershynin. Privacy of synthetic data: a statistical framework. TOIT, 69(1): 0 520--527, 2023

    2023

  11. [11]

    R. E. Bryant. Symbolic B oolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv., 24 0 (3): 0 293--318, 1992

    1992

  12. [12]

    K. Cai, X. Lei, J. Wei, and X. Xiao. Data synthesis via differentially private M arkov random fields. Proc. VLDB Endow., 14 0 (11): 0 2190--2202, 2021

    2021

  13. [13]

    Chow and C

    C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. TOIT, 14 0 (3): 0 462--467, 1968

    1968

  14. [14]

    Cormode, S

    G. Cormode, S. Maddock, E. Ullah, and S. Gade. Synthetic tabular data: Methods, attacks and defenses. In KDD, pages 5989--5998, 2025

    2025

  15. [15]

    Courcelle

    B. Courcelle. The monadic second-order logic of graphs. I . R ecognizable sets of finite graphs. Inf. Comp., 85 0 (1): 0 12--75, 1990

    1990

  16. [16]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015

    2015

  17. [17]

    Dagan and G

    Y. Dagan and G. Kur. A bounded-noise mechanism for differential privacy. In COLT, pages 625--661, 2022

    2022

  18. [18]

    Dawson, B

    M. Dawson, B. Ghazi, P. Kamath, K. Kumar, R. Kumar, B. Luan, P. Manurangsi, N. Mundru, H. Nair, A. Sealfon, et al. Optimizing hierarchical queries for the attribution reporting API . In AdKDD@ KDD, 2023

    2023

  19. [19]

    Djelloul

    S. Djelloul. Treewidth and logical definability of graph products. TCS, 410 0 (8): 0 696--710, 2009

    2009

  20. [20]

    Durfee and R

    D. Durfee and R. M. Rogers. Practical differentially private top- k selection with pay-what-you-get composition. In NIPS, 2019

    2019

  21. [21]

    Dwork and A

    C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9 0 (3-4): 0 211--407, 2014

    2014

  22. [22]

    Dwork, M

    C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC, pages 381--390, 2009

    2009

  23. [23]

    Eppstein

    D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27 0 (3): 0 275--291, 2000

    2000

  24. [24]

    Gaboardi, E

    M. Gaboardi, E. J. G. Arias, J. Hsu, A. Roth, and Z. S. Wu. Dual query: Practical private query release for high dimensional data. In ICML, pages 1170--1178, 2014

    2014

  25. [25]

    Ghazi, R

    B. Ghazi, R. Kumar, and P. Manurangsi. On avoiding the union bound when answering multiple differentially private queries. In COLT, pages 2133--2146, 2021

    2021

  26. [26]

    Ghazi, P

    B. Ghazi, P. Kamath, R. Kumar, P. Manurangsi, and K. Wu. On differentially private counting on trees. In ICALP, pages 66:1--66:18, 2023

    2023

  27. [27]

    Ghazi, C

    B. Ghazi, C. Guzm\' a n, P. Kamath, A. Knop, R. Kumar, P. Manurangsi, and S. Sachdeva. PREM : Privately answering statistical queries with relative error. In COLT, pages 2460--2460, 2025

    2025

  28. [28]

    Gonz\' a lez, C

    T. Gonz\' a lez, C. Guzm\' a n, and C. Paquette. Mirror descent algorithms with nearly dimension-independent rates for differentially-private stochastic saddle-point problems. SIAM J. Optim., 36 0 (1): 0 233--262, 2026

    2026

  29. [29]

    Gr \"o tschel, L

    M. Gr \"o tschel, L. Lov \'a sz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1 0 (2): 0 169--197, 1981

    1981

  30. [30]

    Hardt and G

    M. Hardt and G. N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In FOCS, pages 61--70, 2010

    2010

  31. [31]

    Hardt, K

    M. Hardt, K. Ligett, and F. McSherry. A simple and practical algorithm for differentially private data release. In NIPS, pages 2348--2356, 2012

    2012

  32. [32]

    J. Hsu, A. Roth, and J. Ullman. Differential privacy for the analyst via private equilibrium computation. In STOC, pages 341--350, 2013

    2013

  33. [33]

    Koller and N

    D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009

    2009

  34. [34]

    Korhonen

    T. Korhonen. A single-exponential time 2-approximation algorithm for treewidth. In FOCS, pages 184--192, 2021

    2021

  35. [35]

    C. J. Lebeda, A. Nikolov, and H. Tang. Weighted F ourier factorizations: Optimal G aussian noise for differentially private marginal and product queries. In PODS, 2026

    2026

  36. [36]

    Li and G

    C. Li and G. Miklau. Optimal error of query sets under the differentially-private matrix mechanism. In EDBT/ICDT, pages 272--283, 2013

    2013

  37. [37]

    R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36 0 (2): 0 177--189, 1979

    1979

  38. [38]

    Mckenna, D

    R. Mckenna, D. Sheldon, and G. Miklau. Graphical-model based estimation and inference for differential privacy. In ICML, pages 4435--4444, 2019

    2019

  39. [39]

    McKenna, G

    R. McKenna, G. Miklau, and D. Sheldon. Winning the NIST contest: A scalable and general approach to differentially private synthetic data. J. Priv. Conf., 11 0 (3), 2021

    2021

  40. [40]

    McKenna, B

    R. McKenna, B. Mullins, D. Sheldon, and G. Miklau. AIM : an adaptive and iterative mechanism for differentially private synthetic data. In VLDB, pages 2599--2612, 2022

    2022

  41. [41]

    McSherry and K

    F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, pages 94--103, 2007

    2007

  42. [42]

    G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44 0 (1): 0 1--29, 1997

    1997

  43. [43]

    Mohri, A

    M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. The MIT Press, 2nd edition, 2018

    2018

  44. [44]

    K. P. Murphy. Machine Learning: A Probabilistic Perspective. MIT Press, 2012

    2012

  45. [45]

    A. Nikolov. Private query release via the J ohnson-- L indenstrauss transform. In SODA, pages 4982--5002, 2023

    2023

  46. [46]

    Nikolov and J

    A. Nikolov and J. Ullman. Open problem - optimal query release for pure differential privacy. DifferentialPrivacy.org, 07 2021. https://differentialprivacy.org/open-problem-optimal-query-release/

    2021

  47. [47]

    Nikolov, K

    A. Nikolov, K. Talwar, and L. Zhang. The geometry of differential privacy: the sparse and approximate cases. In STOC, pages 351--360, 2013

    2013

  48. [48]

    S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res., 20 0 (2): 0 257–301, 1995

    1995

  49. [49]

    Ponomareva, Z

    N. Ponomareva, Z. Xu, H. B. McMahan, P. Kairouz, L. Rosenblatt, V. Cohen-Addad, C. Guzmán, R. McKenna, G. Andrew, A. Bie, D. Yu, A. Kurakin, M. Zadimoghaddam, S. Vassilvitskii, and A. Terzis. How to DP-fy your data: A practical guide to generating synthetic data with differential privacy. arXiv, 2512.03238, 2025

    Pith/arXiv arXiv 2025

  50. [50]

    Samer and S

    M. Samer and S. Szeider. Constraint satisfaction with bounded treewidth revisited. JCSS, 76 0 (2): 0 103--114, 2010

    2010

  51. [51]

    Ullman and S

    J. Ullman and S. P. Vadhan. PCPs and the hardness of generating private synthetic data. In TCC, 2011

    2011

  52. [52]

    S. Vadhan. The Complexity of Differential Privacy, pages 347--450. Springer, 2017

    2017

  53. [53]

    Vietri, G

    G. Vietri, G. Tian, M. Bun, T. Steinke, and Z. S. Wu. New oracle-efficient algorithms for private synthetic data release. In ICML, pages 9765--9774, 2020

    2020

  54. [54]

    Zhang, G

    J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and X. Xiao. PrivBayes : Private data release via B ayesian networks. TODS, 42 0 (4), 2017

    2017