[Busec] Fwd: Friday Theory Seminar: Jon Ullman at 3:00PM - Hardness of Generating Private Synthetic Data

Sharon Goldberg goldbe at cs.bu.edu
Mon Feb 14 14:01:13 EST 2011


Hi BUsec - Interesting recent theory work on Differential Privacy,
this Friday at 3PM:

---------- Forwarded message ----------
From: Steve Homer <homer at cs.bu.edu>
Date: Mon, Feb 14, 2011 at 10:53 AM
Subject: Friday Theory Seminar: Jon Ullman at 3:00PM - Hardness of
Generating Private Synthetic Data
To: Steve Homer <homer at cs.bu.edu>




                             COLLOQUIUM

            Computer Science Department and BU RISCS Center
                          Boston University


Speaker: Jon Ullman
        Harvard University

Date:   Friday, February 18
Time:   3:00 PM
Place:  Room MCS 135
       111 Cummington Street

Title:  PCPs and the Hardness of Generating Private Synthetic Data

Abstract:

We study the computational complexity of differentially private data
release for simple, natural queries.  Without computational
constraints, the work of Blum, Ligett, and Roth (STOC '08) showed that
it is possible to produce differentially private "synthetic databases"
that approximately preserve rich classes of statistics about the
original database.  Dwork et. al. (STOC '09) showed that the
inefficiency of this mechanism is inherent for certain families of
queries, but left open whether or not simple statistics can be
approximately preserved efficiently and with differential privacy.

We extend the hardness results of Dwork et. al. to simple, natural
families of queries.  In particular, 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}^n)^d and outputs
a synthetic database D' all of whose two-way marginals are approximately
equal to those of D. (A two-way marginal is the fraction of database
rows x in {0,1}^d with a given pair of values in a given pair of columns.)
Our proof combines a construction of hard-to-sanitize databases based
on digital signatures from Dwork et. al. with encodings based on the
PCP Theorem.

Joint work with Salil Vadhan.





-- 
Sharon Goldberg
Computer Science, Boston University
http://www.cs.bu.edu/~goldbe



More information about the Busec mailing list