Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
Classical · centered · arbitrary width · inverse-polynomial error
One centered sample; (1+1/f(n),2^{-f(n)}) accuracy for polynomial f
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Gaussian Difference Dynamics: Breaking the 2^(n/2) Barrier for the Shortest Vector Problem and Discrete Gaussian SamplingePrint 2026/2690SourceBibTeX / detailsclassical provable worst case DGS centered arbitrary width inverse-polynomial error | 3 Nov 2026 | 20.4130n+o(n) per sample | 20.3138n+o(n) | PreprintSource checked |
| 2 | Discrete Gaussian Sampling Reduces to CVP and SVPSODA 2016SourceBibTeX / detailsclassical worst case centered arbitrary width sparsification dimension-preserving reduction inverse-polynomial error historical claim proof gap reported | 24 Jun 2015 | Claimed 2n+o(n) expected total time, using ADRS15 as the SVP oracle | 2n+o(n) with the ADRS15 oracle | PublishedDisputed |
Comparison definition & assumptions
- Regime
- One centered sample; (1+1/f(n),2^{-f(n)}) accuracy for polynomial f
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Arbitrary-width centered DGS with inverse-polynomial statistical accuracy.
- Comparison rules
- For any positive width, produce a distribution within 2^{-f(n)} of a pointwise (1+1/f(n))-multiplicative approximation. f is polynomial, so implied total-variation accuracy is inverse polynomial. Do not merge with negligible-error DGS without a separate argument.
- Tags
- centered, arbitrary width, inverse-polynomial error