Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
Above smoothing · batch sampling
DGS above the lattice smoothing parameter; output 2^{n/2} samples
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian SamplingSTOC 2015SourceBibTeX / detailsclassical provable worst case DGS above smoothing batch sampling | 26 Dec 2014 | 20.5 n + o(n) | 20.5 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- DGS above the lattice smoothing parameter; output 2^{n/2} samples
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Sampling above smoothing with the full exponential output batch charged to the running time.
- Comparison rules
- Fix an output batch of 2^{n/2} discrete Gaussian samples. Count total preprocessing, sampling time and space. Preserve the smoothing-parameter restriction and error guarantee of the cited theorem.
- Tags
- classical, provable, worst case, DGS, above smoothing, batch sampling