Private Data Release via Learning Thresholds
  This work considers computationally efficient privacy-preserving data
release. We study the task of analyzing a database containing sensitive
information about individual participants. Given a set of statistical queries
on the data, we want to release approximate answers to the queries while also
guaranteeing differential privacy---protecting each participant's sensitive
data.
  Our focus is on computationally efficient data release algorithms; we seek
algorithms whose running time is polynomial, or at least sub-exponential, in
the data dimensionality. Our primary contribution is a computationally
efficient reduction from differentially private data release for a class of
counting queries, to learning thresholded sums of predicates from a related
class.
  We instantiate this general reduction with a variety of algorithms for
learning thresholds. These instantiations yield several new results for
differentially private data release. As two examples, taking {0,1}^d to be the
data domain (of dimension d), we obtain differentially private algorithms for:
  (*) Releasing all k-way conjunctions. For any given k, the resulting data
release algorithm has bounded error as long as the database is of size at least
d^{O(\sqrt{k\log(k\log d)})}. The running time is polynomial in the database
size.
  (*) Releasing a (1-\gamma)-fraction of all parity queries. For any \gamma
\geq \poly(1/d), the algorithm has bounded error as long as the database is of
size at least \poly(d). The running time is polynomial in the database size.
  Several other instantiations yield further results for privacy-preserving
data release. Of the two results highlighted above, the first learning
algorithm uses techniques for representing thresholded sums of predicates as
low-degree polynomial threshold functions. The second learning algorithm is
based on Jackson's Harmonic Sieve algorithm [Jackson 1997].
