Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
Classical · shifted · above smoothing · 2^{0.2075n} batch
Jointly independent shifted-Gaussian approximation; s >= 3 eta_{1/2}(L)/2
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 batch | 3 Nov 2026 | (3/2)n/2+o(n) total batch time | (4/3)n/2+o(n) including outputs | PreprintSource checked |
Comparison definition & assumptions
- Regime
- Jointly independent shifted-Gaussian approximation; s >= 3 eta_{1/2}(L)/2
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Total resource cost for floor((4/3)^{n/2}) samples at a fixed width threshold.
- Comparison rules
- Batch size is floor(2^{beta n}), beta=(1/2)log_2(4/3); compare total cost, not amortized single-sample cost. The older ADRS batch has 2^{n/2} outputs and remains in a different list.
- Tags
- shifted, above smoothing, batch