ECCC-Report TR14-125https://eccc.weizmann.ac.il/report/2014/125Comments and Revisions published for TR14-125en-usThu, 09 Oct 2014 13:57:12 +0300
Paper TR14-125
| Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums |
Anindya De
https://eccc.weizmann.ac.il/report/2014/125In this paper, we construct pseudorandom generators for the class of \emph{combinatorial sums}, a class of functions first studied by \cite{GMRZ13}
and defined as follows: A function $f: [m]^n \rightarrow \{0,1\}$ is said to be a combinatorial sum if there exists functions $f_1, \ldots, f_n: [m] \rightarrow \{0,1\}$ such that
$f(x_1, \ldots, x_n) =f_1(x_1) + \ldots + f_n(x_n)$. Derandomization of combinatorial sums generalize previously studied classes such as combinatorial rectangles~\cite{EGLNV92}, small-biased spaces~\cite{NN93} and modular sums~\cite{LRTV09} among others.
In this work, we present a pseudorandom generator for combinatorial sums with seed length $O(\log m + \log^{3/2}(n/\epsilon))$, thus improving upon \cite{GMRZ13} whenever $\epsilon \le 2^{-(\log n)^{3/4}}$. As a corollary, this gives the first improvement over the INW generator~\cite{INW94} for \emph{fooling} the simple majority function in the case of inverse polynomial error.
The main technical ingredient in our result is the use of \emph{asymptotic expansions} which roughly speaking, are refinements of the classical central limit theorem which achieve a faster convergence rate than the central limit theorem by using more moments for the approximation. While asymptotic version of such theorems have been known in the probability theory literature for some time, explicit bounds were not known for sum of lattice-valued i.i.d.~random variables. In the main technical ingredient of this paper, we prove a new asymptotic expansion theorem for sums of lattice-valued independent random variables (even for the non i.i.d.~case). Given the far-reaching consequences of the central limit theorem in theoretical computer science, we hope that the new \emph{asymptotic expansions} will be of independent interest.
Thu, 09 Oct 2014 13:57:12 +0300https://eccc.weizmann.ac.il/report/2014/125