Computer Science/Discrete Mathematics Seminar II

Asymptotic expansions of the central limit theorem and its applications

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.

Date & Time

November 11, 2014 | 10:30am – 12:30pm

Location

S-101

Affiliation

Center for Discrete Mathematics and Theoretical Computer Science; Visitor, School of Mathematics