Asymptotic expansions of the central limit theorem and its applications

Computer Science/Discrete Mathematics Seminar II
Topic:Asymptotic expansions of the central limit theorem and its applications
Speaker:Anindya De
Affiliation:Center for Discrete Mathematics and Theoretical Computer Science; Visitor, School of Mathematics
Date:Tuesday, November 11
Time/Room:10:30am - 12:30pm/S-101
Video Link:http://video.ias.edu/csdm/2014/1111-AnindyaDe

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.