[Busec] Salil Vadhan at MIT

Sharon Goldberg goldbe at cs.bu.edu
Wed Apr 6 22:51:33 EDT 2011

 Talk by Salil Vadhan on differential privacy at MIT. Definitely highly
theoretical and likely to be very interesting...

Sharon, on iPhone.


Date:       Monday April 11th, 2011
Speaker:  Prof. Salil Vadhan (Harvard University)
Time:      4:30 PM
Location: MIT, Building 2, Room 105

Title:       Computational Complexity in Differential Privacy

An exciting recent line of work in theoretical computer science has
developed a new notion of privacy for computing on databases with sensitive
information, known as “differential privacy.” It requires that no
individual’s data should have a significant influence on the distribution of
the (randomized) output. This is a strong privacy notion that is robust to
auxiliary information available to an adversary, yet it has been shown to
require only a small cost in accuracy for many computations of interest.

In this talk, I will describe how computational resource constraints can
affect the achievability of differential privacy. We will consider both
resource constraints on the data curator (making privacy harder to achieve)
and on the adversary (making privacy easier to achieve). For the former, we
show that it is computationally intractable to generate differentially
private “synthetic data” that preserves even very simple statistics (2-way
marginals), even though much more is possible without computational
constraints. For the latter, we show that a computational relaxation of
differential privacy (where we only consider computationally bounded
adversaries) allows for significantly more accurate 2-party protocols for
estimating the Hamming distance between two binary vectors.

Based on joint works with Cynthia Dwork, Andrew McGregor, Ilya Mironov, Moni
Naor, Omer Reingold, Guy Rothblum, Omkant Pandey, Toni Pitassi, Kunal
Talwar, and Jon Ullman.


Applied Math Colloquium Website: http://www-math.mit.edu/amc/spring11
Applied Math Colloquium poster:
To sign up for Applied Mathematics Colloquium announcements, please contact
avisha at math.mit.edu

Massachusetts Institute of Technology
Department of Mathematics
Cambridge, MA 02139
Math Department: http://math.mit.edu

Cis-seminars mailing
listCis-seminars at lists.csail.mit.eduhttps://lists.csail.mit.edu/mailman/listinfo/cis-seminars

Theory-seminars mailing list
Theory-seminars at lists.csail.mit.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://cs-mailman.bu.edu/pipermail/busec/attachments/20110406/265cf0d0/attachment.html 

More information about the Busec mailing list