Finding a Shortest Vector and More in 2^(n/2+o(n)) Time using q-ary Coset Difference Tree

Minki Hhan

ePrint 2026/1859

Time bound

2^{n/2 + o(n)}

Space bound

2^{0.5 n + o(n)}

Source / version date

2 Sept 2026

Comparison variant

Constant approximation · large-factor limit

Cost scale

2^{(c + ε) n}, any fixed ε > 0

Norm

Euclidean ℓ₂

Success guarantee

High probability

Computation model

Classical randomized; polynomial factors suppressed

reference

Hhan26b

Approximation guarantee

Exact output (μ = 1), hence meets every relaxed constant-factor guarantee

Assumptions and source notes

The exact-SVP theorem immediately supplies this approximation guarantee without changing time or space. This is a transferred guarantee, not another algorithm or a separate new result. Preprint claim: exact worst-case SVP in time and space 2^{n/2+o(n)}. Its separate distance-guarantee CVP result is not treated as unrestricted exact CVP here. Source checked; proof not independently audited.

Primary source ↗

@misc{paper-0f3a0f011219,
  author = {Minki Hhan},
  title = {{Finding a Shortest Vector and More in 2^(n/2+o(n)) Time using q-ary Coset Difference Tree}},
  year = {2026},
  url = {https://arxiv.org/abs/2609.02764},
  cr_date = {2026-09-02},
  cr_status = {preprint},
  cr_author_ids = {minki-hhan},
  howpublished = {arXiv:2609.02764; also Cryptology ePrint Archive, Paper 2026/1859}
}