Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums

Anindya De*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We prove a new asymptotic expansion in the central limit theorem for sums of discrete independent random variables. The classical central limit theorem asserts that if {Xi}n i=1 is a sequence of n i.i.d. Random variables, then S = ≥ n i=1 Xi converges to a Gaussian whose first two moments match those of S. Further, the rate of convergence is O(n - 1/2) Roughly speaking, asymptotic expansions of the central limit theorem show that by considering a family of limiting distributions specified by k ≥ 2 (k=2 corresponds to Gaussians) and matching the first k moments of S to such a limiting distribution, one can achieve a convergence of n - (k - 1)/2. While such asymptotic expansions have been known since Cramer, they did not apply to discrete and non-identical random variables. Further, the error bounds in nearly all cases was non-explicit (in their dependence on {Xi}), thus limiting their applicability. In this work, we prove a new asymptotic expansions of the central limit theorem which applies to discrete and non-identical random variables and the error bounds are fully explicit. Given the wide applicability of the central limit theorem in probability theory and theoretical computer science, we believe that this new asymptotic expansion theorem will be applicable in several settings. As a main application in this paper, we give an application in derandomization: Namely, we construct PRGs for the class of combinatorial sums, a class of functions first studied by [GMRZ13] and which generalize many previously studied classes such as combinatorial rectangles, small-biased spaces and modular sums among others. A function f : [m]n → {0, 1} is said to be a combinatorial sum if there exists functions f1, fn : [m] → {0, 1} such that f(x1, xn) = f1(x1) ++ fn(xn). For this class, we give a seed length of O(logm + log3/2 (n/∈)), thus improving upon [2] whenever ∈ ≤ 2 - )logn)3/4.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PublisherIEEE Computer Society
Pages883-902
Number of pages20
ISBN (Electronic)9781467381918
DOIs
StatePublished - Dec 11 2015
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: Oct 17 2015Oct 20 2015

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2015-December
ISSN (Print)0272-5428

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
CountryUnited States
CityBerkeley
Period10/17/1510/20/15

Keywords

  • Central limit theorem
  • asymptotic expansions
  • derandomization

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums'. Together they form a unique fingerprint.

Cite this