<div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div>Just a reminder for Zhenming Liu&#39;s talk on Oblivious RAM, tomorrow 10-11AM in the Hariri Institute.  See you then!</div>


<div><br></div><div>Sharon</div><div><br></div><div> BUsec Calendar:  <a href="http://www.bu.edu/cs/busec/" target="_blank">http://www.bu.edu/cs/busec/</a></div><div> BUsec Mailing list:  <a href="http://cs-mailman.bu.edu/mailman/listinfo/busec" target="_blank">http://cs-mailman.bu.edu/mailman/listinfo/busec</a></div>




<div> How to get to BU from MIT:  Try the CT2 bus or MIT&#39;s &quot;Boston Daytime</div><div> Shuttle&quot; <a href="http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html" target="_blank">http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html</a></div>




<div><br></div><div>****</div><div>Title: Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead</div><div>Speaker: Zhenming Liu, Princeton University</div><div>Monday, December 16, 10am – 11:30am</div><div>*HARIRI INSTITUTE*, Room MCS180, 111 Cummington St, Boston MA</div>




<div><br></div><div>We demonstrate a simple, statistically secure, ORAM with computational overhead $\tilde{O}(\log^2 n)$; previous ORAM protocols achieve only computational security (under computational assumptions) or require $\tilde{\Omega}(\log^3 n)$ overheard. An additional benefit of our ORAM is its conceptual simplicity, which makes it easy to implement in both software and (commercially available) hardware.</div>




<div><br></div><div>Our construction is based on recent ORAM constructions due to Shi, Chan, Stefanov, and Li (Asiacrypt 2011) and Stefanov and Shi (ArXiv 2012), but with some crucial modifications in the algorithm that simplifies the ORAM and enable our analysis. A central component in our analysis is reducing the analysis of our algorithm to a ``supermarket&#39; problem; of independent interest (and of importance to our analysis,) we provide an upper bound on the rate of ``upset&#39;&#39; customers in the ``supermarket&#39;&#39; problem.</div>




<div><br></div><div><br></div><div>****</div><div><br></div><div>[Privacy Year Event]</div><div>Title: (Nearly) Optimal Differentially Private Singular Subspace Computation</div><div>Speaker: Abhradeep Guha Thakurta, Stanford University and Microsoft Research</div>




<div>Wednesday, December 18, 10am – 11:30am</div><div>MCS137, 111 Cummington St, Boston MA</div><div><br></div><div>Abstract: In this work we study the problem of releasing the principal rank-k right singular subspace for a given matrix A\in R^{m x n} while preserving differential privacy. We study the problem in the context where each row of A is the private information belonging to an individual. We show that there exists an (\epsilon,\delta)-differentially private algorithm that can capture almost all the variance of A captured by  the true principal rank-k right singular subspace, up to an additive error of O(k\sqrt n). We further show that the error can be significantly improved if the eigen spectrum of A^T A has a gap of \omega(\sqrt n) between k-th and (k+1)-th eigen values. As a corollary, we show that under the eigen gap above, the private subspace converges to the non-private subspace as m-&gt;\infty.</div>




<div><br></div><div>We also study the subspace estimation problem in the online setting, where the rows of the matrix arrive online. Using a variant of the Follow the Perturbed Leader algorithm of Kalai and Vempala, 2005, we manage to obtain a differentially private algorithm which has (nearly) optimal error (regret).</div>




<div><br></div><div>Finally, using the recent lower bounding technique of Bun, Ullman and Vadhan, 2013, we show that our results are essentially tight, both in the offline and the online setting.</div><div><br></div><div>




Joint work with: Cynthia Dwork, Kunal Talwar and Li Zhang.</div><div></div></div>
</div></div>
</div></div>