Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
STOC 2015
- Time bound
- 2n/2+o(n) for gap factor γ = 1.93
- Space bound
- 20.5 n + o(n)
- Source / version date
- 26 Dec 2014
- Comparison variant
- Approximate decision · Euclidean
- Cost scale
- Parameterized time bound in n and gap factor γ
- Norm
- Euclidean ℓ₂
- Approximation factor
- γ = 1.93
- Problem variant
- Promise decision: λ₁(L) ≤ r versus λ₁(L) > γr
- Computation model
- Randomized classical
- reference
- ADRS15
- timeExponentAtStatedGuarantee
- 0.5
Assumptions and source notes
The above-smoothing sampler implies a 1.93-approximate decision-SVP algorithm in the stated total time and space. The source does not claim an approximate shortest vector with this cost. The factor is retained as an entry parameter; bounds for different gap factors are not assigned a common numerical rank.
Source location
Abstract, above-smoothing DGS and 1.93-approximate decision-SVP consequence
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}
}