<div bgcolor="#FFFFFF">
<div>Talk by Salil Vadhan on differential privacy at MIT. Definitely highly theoretical and likely to be very interesting...<br><br>Sharon, on iPhone.  </div>
<div><br>MIT APPLIED MATHEMATICS COLLOQUIUM<br></div>
<blockquote type="cite">
<div>
<blockquote type="cite">
<blockquote type="cite">
<div>
<div>
<div>
<div>
<p class="MsoNormal"><br>Date:       Monday April 11th, 2011<br>Speaker:  Prof. Salil Vadhan (Harvard University)<br>Time:      4:30 PM <br>Location: MIT, Building 2, Room 105 <br><br>Title:       Computational Complexity in Differential Privacy<br>

<br>Abstract: <br><span style="FONT-SIZE: 11pt">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.</span> </p>


<p class="MsoNormal"><span style="FONT-SIZE: 11pt">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.  </span></p>


<p class="MsoNormal"><span style="FONT-SIZE: 11pt">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.</span></p>


<p class="MsoNormal">****** <br><br>Applied Math Colloquium Website: <a href="http://www-math.mit.edu/amc/spring11" target="_blank"><a href="http://www-math.mit.edu/amc/spring11" target="_blank">http://www-math.mit.edu/amc/spring11</a></a> <br>

Applied Math Colloquium poster: <a href="http://www-math.mit.edu/amc/spring11/S_Vadhan.pdf" target="_blank"><a href="http://www-math.mit.edu/amc/spring11/S_Vadhan.pdf" target="_blank">http://www-math.mit.edu/amc/spring11/S_Vadhan.pdf</a></a><br>

To sign up for Applied Mathematics Colloquium announcements, please contact <a href="mailto:avisha@math.mit.edu" target="_blank"><a href="mailto:avisha@math.mit.edu" target="_blank">avisha@math.mit.edu</a></a> <br><br>Massachusetts Institute of Technology <br>

Department of Mathematics <br>Cambridge, MA 02139 <br>Math Department: <a href="http://math.mit.edu/" target="_blank"><a href="http://math.mit.edu/" target="_blank">http://math.mit.edu</a></a> </p>
<div>
<p class="MsoNormal"> </p></div></div></div>
<p class="MsoNormal"> </p></div>
<p class="MsoNormal"> </p></div></blockquote><br><pre><fieldset></fieldset>
_______________________________________________
Cis-seminars mailing list
<a href="mailto:Cis-seminars@lists.csail.mit.edu" target="_blank"><a href="mailto:Cis-seminars@lists.csail.mit.edu" target="_blank">Cis-seminars@lists.csail.mit.edu</a></a>
<a href="https://lists.csail.mit.edu/mailman/listinfo/cis-seminars" target="_blank"><a href="https://lists.csail.mit.edu/mailman/listinfo/cis-seminars" target="_blank">https://lists.csail.mit.edu/mailman/listinfo/cis-seminars</a></a>
</pre></blockquote><br></div></blockquote>
<blockquote type="cite">
<div><span>_______________________________________________</span><br><span>Theory-seminars mailing list</span><br><span><a href="mailto:Theory-seminars@lists.csail.mit.edu" target="_blank">Theory-seminars@lists.csail.mit.edu</a></span><br>

<span><a href="https://lists.csail.mit.edu/mailman/listinfo/theory-seminars" target="_blank">https://lists.csail.mit.edu/mailman/listinfo/theory-seminars</a></span><br></div></blockquote></div>