Metraipolis › archive › dc_ed260b06f46e
One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time — arXiv:2608.03220
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.03220
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T13:09:32.591Z
- SHA-256 of the archived text
de286d3304af7f81daa1ce734493ff59cb681d32aa9ffecc6ad81ebe6d84d30d- Stable URL of this page
https://metraipolis.com/documento/dc_ed260b06f46e
How to cite
One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time — arXiv:2608.03220 — arXiv (en), https://arxiv.org/abs/2608.03220 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ed260b06f46e (Metraipolis archive dc_ed260b06f46e, sha256 de286d3304af7f81daa1ce734493ff59cb681d32aa9ffecc6ad81ebe6d84d30d)
BibTeX
@misc{dced260b06f46e,
title = {One Discrete Gaussian Sample in $2^n/2+o(n)$ Time — arXiv:2608.03220},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.03220},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ed260b06f46e; sha256 de286d3304af7f81daa1ce734493ff59cb681d32aa9ffecc6ad81ebe6d84d30d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.03220. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $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-$n$ lattice $L\subseteq\R^n$ specified by a rational basis and every rational $s^2>0$, we produce one sample from $D_{L,s}$ within statistical distance $\exp(-\Omega(n^3))$ in expected $2^{n/2+o(n)}$ time and $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 $L$; a Gaussian-mass comparison shows that the $2^{n/2}$ samples produced by one ADRS call contain a point of $L$ with inverse-polynomial probability. The factor $2^{n/2}$ is tight in this Gaussian-mass comparison. For every fixed rational $\alpha<1.4697$, the same comparison gives a sub-$2^n$ algorithm for exact CVP on targets satisfying $\dist(y,L)\le\alpha\lambda_1(L)$, without a uniqueness assumption, and an exact-SVP algorithm in $2^{0.7315n+o(n)}$ time.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-05 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.03220 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T12:57:43.018Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).