<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="">REMINDER:<div class=""><br class=""></div><div class=""><p class="MsoNormal" style="font-family: LucidaGrande;"><span class="" style="font-family: 'Times New Roman';">Department of Computer Science & Mathematics</span></p><p class="MsoNormal" style="font-family: LucidaGrande;"><span class="" style="font-family: 'Times New Roman';">Combinatorics & Theoretical Seminar</span></p><p class="MsoNormal" style="font-family: LucidaGrande;"><b class=""><span class="" style="font-family: 'Times New Roman';"> </span></b><b class=""><font face="Times New Roman" class="">Rocco Servedio </font></b><b class=""><span class="" style="font-family: 'Times New Roman';">(Columbia University)</span></b></p><p class="MsoNormal" style="font-family: LucidaGrande;"><b class=""><span class="" style="font-family: 'Times New Roman';">Tuesday, November 14, 2017</span></b></p><p class="MsoNormal" style="font-family: LucidaGrande;"><b class=""><span class="" style="font-family: 'Times New Roman';">Ryerson 251 @ 3:30 pm<o:p class=""></o:p></span></b></p><p class="MsoNormal" style="font-family: LucidaGrande;"><span class="" style="font-family: 'Times New Roman';">Title: Fooling Intersections of low-weight halfspaces</span></p><p class="MsoNormal" style="font-family: LucidaGrande;"><span class="" style="font-family: 'Times New Roman';">Abstract:</span></p><p class="MsoNormal" style="font-family: LucidaGrande;"><span class="" style="font-family: 'Times New Roman';">A weight-$t$ halfspace is a Boolean function $f(x)=\mathrm{sign}(w_1 x_1 + \cdots + w_n x_n - \theta)$ where each $w_i$ is an integer in $\{-t,\dots,t\}.$ We give an explicit pseudorandom generator that $\delta$-fools any intersection of $k$ weight-$t$ halfspaces with seed length poly$(\log n, \log k,t,1/\delta)$. In particular, our result gives an explicit PRG that fools any intersection of any quasipoly$(n)$ number of halfspaces of any polylog$(n)$ weight to any $1/$polylog$(n)$ accuracy using seed length polylog$(n).$<br class=""><br class="">Prior to this work no explicit PRG with seed length $o(n)$ was known even for fooling intersections of $n$ weight-1 halfspaces to constant accuracy.<br class=""><br class="">Our analysis introduces new coupling-based ingredients into the standard Lindeberg method for establishing quantitative central limit theorems and associated pseudorandomness results.<br class=""><br class="">Joint work with Li-Yang Tan.</span><span class="" style="font-family: 'Times New Roman';"> </span></p><p class="MsoNormal" style="font-family: LucidaGrande;"><span class="" style="font-family: 'Times New Roman';">Host: Prof. Li-Yang Tan<o:p class=""></o:p></span></p><p class="MsoNormal" style="font-family: LucidaGrande;"><span class="" style="font-family: 'Times New Roman';">(Refreshments will be served prior to the talk in Ry. 255 @ 3pm)<o:p class=""></o:p></span></p><p class="MsoNormal" style="font-family: LucidaGrande;"><o:p class=""> </o:p></p></div></body></html>