Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JONATHAN ULLMAN:
All reports by Author Jonathan Ullman:

TR10-017 | 10th February 2010
Jonathan Ullman, Salil Vadhan

PCPs and the Hardness of Generating Synthetic Data

Revisions: 4

Assuming the existence of one-way functions, we show that there is no
polynomial-time, differentially private algorithm $A$ that takes a database
$D\in (\{0,1\}^d)^n$ and outputs a ``synthetic database'' $\hat{D}$ all of whose two-way
marginals are approximately equal to those of $D$. (A two-way marginal is the fraction
of database rows ... more >>>




ISSN 1433-8092 | Imprint