BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Talks.cam//talks.cam.ac.uk// X-WR-CALNAME:Talks.cam BEGIN:VEVENT SUMMARY:The Price of Online Queries in Differential Privacy - Mark Bun (Pr inceton University) DTSTART:20161208T120000Z DTEND:20161208T123000Z UID:TALK69392@talks.cam.ac.uk CONTACT:INI IT DESCRIPTION: Co-authors: Thomas Steinke (IBM Research - Al maden)\, Jonathan Ullman (Northeastern University)
&nb sp\;
We consider the problem of answering queries about a sensitive dat aset subject to differential privacy. The queries may be chosen adversari ally from a larger set of allowable queries via one of three interactive models. These models capture whether the queries are given to the mechan ism all in a single batch (&ldquo\;offline&rdquo\;)\, whether they are cho sen in advance but presented to the mechanism one at a time (&ldquo\;onli ne&rdquo\;)\, or whether they may be chosen by an analyst adaptively (&ld quo\;adaptive&rdquo\;).
 \;
Many differentially private mecha nisms are just as efficient in the adaptive model as they are in the offl ine model. Meanwhile\, most lower bounds for differential privacy hold in the offline setting. This suggests that the three models might be equiva lent.
 \;
We prove that these models are all\, in fact\, dist inct. Specifically\, we show that there is a family of statistical querie s such that exponentially more queries from this family can be answered i n the offline model than in the online model. We also exhibit a family of search queries such that many more queries from this family can be answ ered in the online model than in the adaptive model. We also investigate whether such separations might hold for simple queries\, such as threshol d queries over the real line.
 \;
Joint work with Thomas Stei nke and Jonathan Ullman.

Related Links LOCATION:Seminar Room 1\, Newton Institute END:VEVENT END:VCALENDAR