Computer Science/Discrete Mathematics Seminar II

In its simplest form, the central limit theorem states that a sum of n independent random variables can be approximated with error \(O(n^{-1/2})\) by a Gaussian with matching mean and second moment (given these variables are not too dissimilar). We prove an extension of this theorem where we achieve error bounds of \(O(n^{-(s-1)/2})\) by matching \(s\) moments (for any \(s > 0\)). While similar results were known in literature before this, the only explicit error bounds were known when the summands are continuous i.i.d. variables. As an application of this new error bound, we obtain PRGs with seed length \(O(\log^{1.5} n)\) to fool combinatorial shapes with an inverse polynomial error. This provides the first improvement over the results of Nisan and Impagliazzo-Nisan-Wigderson for derandomization of the 'simple majority' function in the case of inverse polynomial error.