Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
STOC 2015
- Time bound
- 2n/2+o(n) total time at radius (0.422−o(1)) λ₁(L)
- Space bound
- 2n/2+o(n)
- Source / version date
- 26 Dec 2014
- Comparison variant
- Classical · total cost · radius dependent
- Cost scale
- Parameterized total time bound in n and decoding radius
- Decoding radius
- (0.422-o(1)) lambda_1(L)
- Preprocessing
- Included: one above-smoothing DGS call and polynomial-time decoding work
- Success guarantee
- Randomized exact decoding under the distance promise; constant success can be amplified
- Cost model
- Classical randomized; total time, not an online-only cost
- timeExponentAtStatedGuarantee
- 0.5
Assumptions and source notes
The first arXiv version already contains this corollary. Above-smoothing Gaussian sampling supplies the dual-vector advice within the displayed total cost. The guarantee is radius (0.422−o(1)) lambda_1(L), not every radius below lambda_1(L)/2. Radius is an entry parameter, so this row is not numerically ranked against a bound for another decoding promise.
Source location
§7.2, Theorem 7.3 and Corollary 7.4; Theorem 5.11
Version: arXiv:1412.7994v1, 26 December 2014
Selected earlier references
Selected sources cited by this paper.
- A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
Daniele Micciancio · Panagiotis Voulgaris · 2013
Uses the previous exact-CVP/Voronoi bound as the comparison point for 1.97-approximate CVP. Abstract; introduction
- On the Closest Vector Problem with a Distance Guarantee
Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2014
Combines the distance-guaranteed decoder with above-smoothing DGS to charge construction of the Gaussian advice and obtain 0.422-BDD in half-exponent total time. §7.2, Theorem 7.3 explicitly attributed to DRS14 Theorem 3.1
@misc{paper-86925aff6e6c,
author = {Divesh Aggarwal and Daniel Dadush and Oded Regev and Noah Stephens-Davidowitz},
title = {{Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling}},
year = {2015},
url = {https://arxiv.org/abs/1412.7994},
cr_date = {2014-12-26},
cr_status = {published},
cr_venue = {STOC 2015},
cr_author_ids = {divesh-aggarwal; daniel-dadush; oded-regev; noah-stephens-davidowitz},
howpublished = {STOC 2015; arXiv:1412.7994}
}