Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
Classical · shifted · above smoothing · one sample
One shifted sample at s >= alpha eta_{1/2}(L), fixed alpha > 1
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 shifted above smoothing single sample | 3 Nov 2026 | (3/2)n/2+o(n) | (4/3)n/2+o(n) | PreprintSource checked |
Comparison definition & assumptions
- Regime
- One shifted sample at s >= alpha eta_{1/2}(L), fixed alpha > 1
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Single-sample algorithms above a specified smoothing threshold.
- Comparison rules
- Return one sample for any rational shift; retain alpha and the actual total-variation guarantee. Do not compare the total cost of unequal output batches as though it were per sample.
- Tags
- shifted, above smoothing, single sample