<div dir="ltr"><div style="font-size:12.8px"><span style="font-size:12.8px">Title: </span><span style="font-size:12.8px">Practical Locally Private Heavy Hitters</span><br></div><div style="font-size:12.8px"><div style="font-size:12.8px">Speaker: Uri Stemmer (Harvard)</div><div style="font-size:12.8px">Wednesday Oct 25, 2017, 10 am - 11 am. </div><div style="font-size:12.8px">BU Hariri Institute Seminar room. 111 Cummington St, Boston MA 02215. </div><div style="font-size:12.8px">Followed by lunch at BUsec lounge.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Abstract:</div><div><div><span style="font-size:12.8px">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.</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">Joint work with Raef Bassily, Kobbi Nissim, and Abhradeep Thakurta.</span></div></div></div><div><br></div>
</div>