[Colloquium] Theory Seminars at Computer Science
Donna Brooms via Colloquium
colloquium at mailman.cs.uchicago.edu
Tue Nov 14 06:49:24 CST 2017
REMINDER:
Department of Computer Science & Mathematics
Combinatorics & Theoretical Seminar
Rocco Servedio (Columbia University)
Tuesday, November 14, 2017
Ryerson 251 @ 3:30 pm
Title: Fooling Intersections of low-weight halfspaces
Abstract:
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).$
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.
Our analysis introduces new coupling-based ingredients into the standard Lindeberg method for establishing quantitative central limit theorems and associated pseudorandomness results.
Joint work with Li-Yang Tan.
Host: Prof. Li-Yang Tan
(Refreshments will be served prior to the talk in Ry. 255 @ 3pm)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20171114/5081708b/attachment.html>
More information about the Colloquium
mailing list