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

Jiseung Kim

arXiv 2608.03220

Time bound

2^n/2+o(n) expected bit operations

Space bound

2^n/2+o(n) bits on every execution

Source / version date

4 Aug 2026

Comparison variant

Arbitrary width · worst case

Cost scale

2^{c n + o(n)}

Width restriction

Any rational s^2 > 0 on a rank-n lattice with rational basis

Output samples

One sample from D_{L,s}

Distribution error

exp(-Omega(n^3)) statistical distance

Computation model

Randomized classical; expected time and bounded space per execution

reference

Kim26

Assumptions and source notes

One centered sample, rather than the older 2^{n/2}-output arbitrary-width batch. Polynomial dependence on basis and squared-width encoding lengths is explicit in the theorem.

Source location

Theorem 4.3, printed p. 10; Theorem 1.1
Version: arXiv:2608.03220v1, 4 August 2026

Primary source ↗

@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}
}