## 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 |

Publisher | IEEE Computer Society |

Pages | 883-902 |

Number of pages | 20 |

ISBN (Electronic) | 9781467381918 |

DOIs | |

State | Published - Dec 11 2015 |

Event | 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States Duration: Oct 17 2015 → Oct 20 2015 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2015-December |

ISSN (Print) | 0272-5428 |

### Other

Other | 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 |
---|---|

Country | United States |

City | Berkeley |

Period | 10/17/15 → 10/20/15 |

## Keywords

- Central limit theorem
- asymptotic expansions
- derandomization

## ASJC Scopus subject areas

- Computer Science(all)