<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div dir="auto" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class="">REMINDER:</font></b></div><div class="" style="font-family: LucidaGrande;"><br class=""></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Department of Mathematics & Computer Science</font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Combinatorics & Theory Seminar</font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class=""><br class=""></font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Tuesday, November 5, 2019</font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Ryerson 251@ 3:30 pm</font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class=""><br class=""></font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class="">Aleksandar Nikolov</font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class="">University of Toronto</font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class=""><br class=""></font></b></div><div class="" style="font-family: LucidaGrande;"><b class=""><font face="TimesNewRomanPSMT" size="4" class=""><span style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class="">Title: The Power of Factorization Mechanisms in Differential Privacy</span><br style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class=""><br style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class=""><span style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class="">Abstract:</span><br style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class=""><br style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class=""><span style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class="">A central goal in private data analysis is to estimate statistics about an unknown distribution from a dataset possibly containing sensitive information, so that the privacy of any individual represented in the dataset is preserved. We study this question in the model of non-interactive local differential privacy (LDP), in which every person in the dataset randomizes their own data in order to preserve its privacy, before sending it to a central server. We give a characterization of the minimum number of samples necessary to get an accurate estimates of a given set of statistical queries, as well as a characterization of the sample complexity of agnostic PAC learning in this model. The characterization is tight up polylogarithmic factors for any given set of statistical queries, and, respectively, any given concept class. The characterization is achieved by a simple and efficient instance-optimal (with respect to the queries/concept class) approximate factorization mechanism, i.e. a mechanism that answers the statistical queries by answering a different set of strategy queries, from which the answers to the original queries can be approximately reconstructed. </span><br style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class=""><br style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class=""><span style="font-family: LucidaGrande; font-size: 14px; font-weight: normal;" class="">Based on joint work with Alexander Edmonds and Jonathan Ullman</span></font></b></div><div class="">
<div style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: inherit; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; font-size: 11px;" class=""><br class="webkit-block-placeholder"></div><div style="color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-variant-east-asian: normal; font-variant-position: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class=""><p class="MsoNormal" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal;"><b class=""><font size="4" class="">Donna Brooms-Blue</font></b></p><br class="Apple-interchange-newline" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;"></div>
</div></div></div></div></div></div><br class=""></div></body></html>