cronokirby

(2026-08) One Discrete Gaussian Sample in 2^{n/2+o(n)} Time

2026-08-04

Abstract

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample 2n/22^{n/2} discrete Gaussians at an arbitrary parameter in 2n+o(n)2^{n+o(n)} time, and above smoothing in 2n/2+o(n)2^{n/2+o(n)} time. They ask whether the latter bound suffices for one sample at an arbitrary parameter. We answer this question affirmatively: for every rank-nn lattice L⊆RnL\subseteq\R^n specified by a rational basis and every rational s2>0s^2>0, we produce one sample from DL,sD_{L,s} within statistical distance \exp(−Ω(n3))\exp(-\Omega(n^3)) in expected 2n/2+o(n)2^{n/2+o(n)} time and 2n/2+o(n)2^{n/2+o(n)} space on every execution. The algorithm samples from random superlattices that are smooth at the required scale with constant probability and outputs the first point in LL; a Gaussian-mass comparison shows that the 2n/22^{n/2} samples produced by one ADRS call contain a point of LL with inverse-polynomial probability. The factor 2n/22^{n/2} is tight in this Gaussian-mass comparison. For every fixed rational α<1.4697\alpha<1.4697, the same comparison gives a sub-2n2^n algorithm for exact CVP on targets satisfying dist⁡(y,L)≤αλ1(L)\operatorname{dist}(y,L)\le\alpha\lambda_1(L), without a uniqueness assumption, and an exact-SVP algorithm in 20.7315n+o(n)2^{0.7315n+o(n)} time.