Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
Classical · shifted · distance-relative width
Shifted Gaussian samples with width above dist(t,L)/f(n)
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!FOCS 2015SourceBibTeX / detailsclassical provable worst case shifted DGS batch distance relative | 29 Sept 2015 | 2n+o(n) when log n log f(n)=o(n) | At most 2n+o(n) storage from the list algorithm | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Shifted Gaussian samples with width above dist(t,L)/f(n)
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Shifted sampling below smoothing, with a remaining distance-relative cutoff.
- Comparison rules
- For efficiently computable superpolynomial f, require s > dist(t,L)/f(n). The coefficient 1 is only normalized when log n log f(n)=o(n). Output count is mass dependent, not a fixed 2^{n/2} batch. This is not all-width shifted DGS.
- Tags
- shifted, below smoothing, batch