[Busec] Seminar Wednesday Oct 25: Practical Locally Private Heavy Hitters

Yilei Chen chenyl at bu.edu
Fri Oct 20 14:46:43 EDT 2017


Title: Practical Locally Private Heavy Hitters
Speaker: Uri Stemmer (Harvard)
Wednesday Oct 25, 2017, 10 am - 11 am.
BU Hariri Institute Seminar room. 111 Cummington St, Boston MA 02215.
Followed by lunch at BUsec lounge.

Abstract:
We present new heavy-hitters algorithms satisfying
local-differential-privacy, with optimal or near-optimal worst-case error
and running time. In our algorithms, the server running time is $\tilde
O(n)$ and user running time is $\tilde O(1)$, hence improving on the prior
state-of-the-art result of Bassily and Smith [STOC 2015] requiring
$O(n^{5/2})$ server time and $O(n^{3/2})$ user time. With a typically large
number of participants in local algorithms ($n$ in the millions), this
reduction in time complexity is crucial for making locally-private
heavy-hitters algorithms usable in practice.

Joint work with Raef Bassily, Kobbi Nissim, and Abhradeep Thakurta.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20171020/1886715b/attachment.html>


More information about the Busec mailing list