<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><span class="" style="font-family: LucidaGrande;"><b class="">REMINDER:</b></span></div><span class=""><div class="" style="font-family: LucidaGrande;"><span class=""><br class=""></span></div>Departments of Computer Science & Mathematics</span><div class="">Combinatorics & Theoretical Seminar</div><div class=""><br class=""></div><div class=""><div class="">Tuesday, May 2, 2017<br class="">Ryerson 251 @ 3pm<br class=""><br class=""><b class="">Rocco Servedio</b><br class="">Columbia University<br class=""><a href="http://www.cs.columbia.edu/~rocco/" class="">http://www.cs.columbia.edu/~rocco/</a><br class=""><br class="">Title: Learning Sums of Independent Commonly Supported Integer Random Variables<br class=""><br class="">Abstract:</div><div class="">For S a finite set of natural numbers, an "S-supported SICSIRV" is a random variable which is the sum of N independent random variables each of which is supported on S. So, for example, if S = {0,1}, then an S-supported SICSIRV is a sum of N independent but not necessarily identically distributed Bernoulli random variables (a.k.a. a Poisson Binomial random variable). Daskalakis et. al. (STOC'12, FOCS'13) have shown that for S={0,1,...,k-1}, there is an algorithm for learning an unknown S-SICSIRV using poly(k,1/\epsilon) draws from the distribution and running in poly(k,1/\epsilon) time, independent of N. <br class=""><br class="">In this work we investigate the problem of learning an unknown S-SICSIRV where S={a_1,...,a_k} may be any finite set. We show that * when k=3, it is possible to learn any S-SICSIRV with poly(1/\epsilon) samples, independent of the values a_1,a_2,a_3; * when k >= 4, it is possible to learn any S-SICSIRV with poly(1/\epsilon, \log \log a_k) samples; and * already when k=4, at least \log \log a_k samples may be required for learning.<br class=""><br class="">We thus establish a sharp transition in the complexity of learning S-SICSIRVs when the size of S goes from three to four.<br class=""><br class="">Joint work with Anindya De and Phil Long.<br class=""><br class="">Host: Prof. Razborov<br class=""><br class="">Refreshments will be served before the talk in Ry 255.</div><div class=""></div></div></body></html>