DGS / Classical · centered · arbitrary width · inverse-polynomial error

Discrete Gaussian Sampling Reduces to CVP and SVP

Noah Stephens-Davidowitz

SODA 2016

PublishedDisputed

Time bound: Claimed 2^n+o(n) expected total time, using ADRS15 as the SVP oracle
Space bound: 2^n+o(n) with the ADRS15 oracle

Source / version date: 24 Jun 2015
Comparison variant: Classical · centered · arbitrary width · inverse-polynomial error
Cost scale: 2^{c n + o(n)}
Width requirement: Any rational s > 0; centered distribution on a rational lattice
Output: One sample
Accuracy convention: (1+1/f(n), 2^{-f(n)})-close for every efficiently computable 1 <= f(n) <= poly(n); implied TV error inverse polynomial
Cost model: Expected-polynomial-time reduction with an exact-SVP oracle; ADRS15 oracle costs included
proof-status: Original radius-grid argument has a reported counterexample; corrected reduction in GHH26 Theorem 12.6 and Appendix D, https://arxiv.org/abs/2611.04336v1

Assumptions and source notes

Historical claim of an expected-polynomial-time, dimension-preserving reduction from arbitrary-width centered DGS to exact SVP on sublattices. Instantiating the claimed reduction with ADRS15 gives coefficient 1, without improving the already known DGS exponent 1. The first arXiv version contains the stated reduction and accuracy guarantee, but GHH26 Appendix D.1 identifies a counterexample to the additive squared-radius grid comparison in this proof; its multiplicative-grid replacement repairs the reduction in 2026. This entry is therefore disputed and excluded from admitted historical bounds and result markers. The exponent 1 itself remains independently supported by the ADRS15 sampler; the issue concerns this particular reduction proof. The multiplicative accuracy is inverse polynomial, not negligible TV error.

Source location

§4.3, Theorem 4.5 and its additive squared-radius grid in the original v1; gap and repair: GHH26 §12.4, Theorem 12.6, Appendix D.1 (printed pp. 89–90)
Version: arXiv:1506.07490v1, 24 June 2015; gap cross-checked against arXiv:2611.04336v1, 3 November 2026

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
Summarizes the arbitrary-width centered batch and above-smoothing sampling contracts before proving oracle reductions. §1.3 and Table 1
Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!
Divesh Aggarwal · Daniel Dadush · Noah Stephens-Davidowitz · 2015
Distinguishes the shifted distance-relative cutoff sampler from all-width shifted DGS. §1.3 and Table 1

Primary source ↗

BibTeXDownload .bib

@inproceedings{stephens-davidowitz-2016-dgs,
  author = {Noah Stephens-Davidowitz},
  title = {{Discrete Gaussian Sampling Reduces to CVP and SVP}},
  booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)},
  year = {2016},
  url = {https://arxiv.org/abs/1506.07490},
  cr_date = {2015-06-24},
  cr_status = {published},
  cr_venue = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)},
  cr_author_ids = {noah-stephens-davidowitz}
}