期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2016
卷号：2016
页码：1-11
DOI：10.4086/cjtcs.2016.007
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：We prove a local central limit theorem for the sum of one-dimensional discrete Gaussians in $n$-dimensional space. In more detail, we analyze the distribution of $\sum_{i=1}^m v_i \mathbf{x}_i$ where $\mathbf{x}_1,\ldots,\mathbf{x}_m$ are fixed vectors from some lattice $\mathcal{L} \subset \mathbb{R}^n$ and $v_1,\ldots,v_m$ are chosen independently from a discrete Gaussian distribution over $\mathbb{Z}$. We show that under a natural constraint on $\mathbf{x}_1,\ldots,\mathbf{x}_m$, if the $v_i$ are chosen from a wide enough Gaussian, the sum is statistically close to a discrete Gaussian over $\mathcal{L}$. We also analyze the case of $\mathbf{x}_1,\ldots,\mathbf{x}_m$ that are themselves chosen from a discrete Gaussian distribution (and fixed). Our results simplify and qualitatively improve upon a recent result by Agrawal, Gentry, Halevi, and Sahai
关键词：Local central limit theorem; Discrete Gaussians; Lattices
