One Discrete Gaussian Sample in 2^{n/2+o(n)} Time
arXiv 2608.03220
- Time bound
- 2c₀ n + o(n), c₀ ≈ 0.7315
- Space bound
- 2n/2 + o(n)
- Source / version date
- 4 Aug 2026
- Comparison variant
- Classical · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- At least 2/3
- Computation model
- Randomized Turing machine; polynomial input-length factors suppressed
- reference
- Theorem 6.6; §6 constants
Assumptions and source notes
The exact-SVP consequence is separate from the paper’s one-sample DGS theorem. Theorem 6.6 gives success probability at least 2/3, time coefficient c₀ = 1/2 + β_Lev²/(4e ln 2) ≈ 0.7315 and space coefficient 1/2 on every execution. This was not an overall time record: Hhan’s 0.6039 result had appeared the preceding day. Source checked; proof not independently audited.
Source location
Abstract; §6 constant definitions, printed p. 17; Theorem 6.6, printed p. 23
Version: arXiv:2608.03220v1, 4 August 2026; original PDF checked
Selected earlier references
Selected sources cited by this paper.
- Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2015
Uses the older above-smoothing batch sampler on superlattices to obtain one arbitrary-width centered sample. Abstract; §1.2; Theorem 2.6
- Solving the Shortest Vector Problem in 2^(0.7314n+o(n)) Time via Discrete Gaussian Sampling on Superlattices
Yiming Gao · Yansong Feng · Honggang Hu · 2026
Independent superlattice-based exact-SVP result; compares 0.7314 with this paper’s 0.7315. §1, Concurrent work; bibliography [GFH26]
- Solving the Shortest Vector Problem in 2^(0.6039n) Time via Mid-point Hessian
Minki Hhan · 2026
Earlier Hessian approach already gives a smaller exact-SVP time exponent. §1, Concurrent work; bibliography [Hha26]
- Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)
Xavier Pujol · Damien Stehlé · 2009
Uses the earlier lattice-point counting bound in the Gaussian-mass analysis. §6, Lemma 6.1 and bibliography [PS09]
@misc{kim-2026-one-dgs,
author = {Jiseung Kim},
title = {{One Discrete Gaussian Sample in 2^{n/2+o(n)} Time}},
year = {2026},
url = {https://arxiv.org/abs/2608.03220},
cr_date = {2026-08-04},
cr_status = {preprint},
cr_author_ids = {jiseung-kim},
archiveprefix = {arXiv},
eprint = {2608.03220}
}