2026/08/04 by Jiseung Kim
Computer Science · #cs.DS
arxiv created 2026/08/04 · arxiv updated 2026/08/05
Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample 2n/2 discrete Gaussians at an arbitrary parameter in 2n+o(n) time, and above smoothing in 2n/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-n lattice L⊆\Rn specified by a rational basis and every rational s2>0, we produce one sample from DL,s within statistical distance exp(-Ω(n3)) in expected 2n/2+o(n) time and 2n/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 L; a Gaussian-mass comparison shows that the 2n/2 samples produced by one ADRS call contain a point of L with inverse-polynomial probability. The factor 2n/2 is tight in this Gaussian-mass comparison. For every fixed rational α<1.4697, the same comparison gives a sub-2n algorithm for exact CVP on targets satisfying \dist(y,L)≤αλ1(L), without a uniqueness assumption, and an exact-SVP algorithm in 20.7315n+o(n) time.