Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-125 | 9th October 2014 02:02

Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums


Authors: Anindya De
Publication: 9th October 2014 13:57
Downloads: 1321


In 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.

ISSN 1433-8092 | Imprint