Fooling intersections of low-weight halfspaces

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
$\mathrm{quasipoly}(n)$ number of halfspaces of any $\mathrm{polylog}(n)$ weight to any
$1/\mathrm{polylog}(n)$ accuracy using seed length $\mathrm{polylog}(n)$. Prior to this work
no explicit PRG with non-trivial seed length was known even for fooling
intersections of $n$ weight-$1$ halfspaces to constant accuracy.

The analysis of our PRG fuses techniques from two different lines of work on
unconditional pseudorandomness for different kinds of Boolean functions. We
extend the approach of Harsha, Klivans, and Meka for fooling
intersections of regular halfspaces, and combine this approach with results of
Bazzi and Razborov on bounded independence
fooling CNF formulas. 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 Rocco Servedio.