DGS · Arbitrary width · worst case

Arbitrary width · worst case

Centered DGS on arbitrary Euclidean lattices; any positive width

3 results · 3 papers

ClassicalProvableWorst case2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	Superlattice methods for the shortest vector problem and discrete Gaussian samplingMinki Hhan · Jiseung Kim · Sunyeop Kim · Thijs LaarhovenePrint 2026/2761Source BibTeX / detailsclassical provable worst case DGS arbitrary width unstructured	4 Nov 2026	2^{0.292 n + o(n)}	2^{0.208 n + o(n)}	PreprintSource checked
2	One Discrete Gaussian Sample in 2^{n/2+o(n)} TimeJiseung KimarXiv 2608.03220Source BibTeX / detailsclassical provable worst case DGS arbitrary width centered single sample	4 Aug 2026	2^n/2+o(n) expected bit operations	2^n/2+o(n) bits on every execution	PreprintSource checked
3	Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian SamplingDivesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-DavidowitzSTOC 2015Source BibTeX / detailsclassical provable worst case DGS arbitrary width unstructured	26 Dec 2014	2^{1 n + o(n)}	2^{1 n + o(n)}	PublishedSource checked

Comparison definition & assumptions

Regime: Centered DGS on arbitrary Euclidean lattices; any positive width
Computation: Classical
Rigor: Provable
Instances: Worst case
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Worst-case total-cost bounds for obtaining a discrete Gaussian sample at an unrestricted width.
Comparison rules: Include preprocessing in total time. Record the output batch size and statistical error per entry; a batch upper bound also bounds the cost of retaining one sample. Do not divide total batch cost into an amortized per-sample score. Large-width-only samplers have a separate category.
Tags: classical, provable, worst case, DGS, arbitrary width, unstructured