Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
STOC 2015
- Time bound
- 2n+o(n) for approximation factor γ = 1.97
- Space bound
- 2n+o(n)
- Source / version date
- 26 Dec 2014
- Comparison variant
- Approximate search · Euclidean
- Cost scale
- Parameterized time bound in n and approximation factor
- Norm
- Euclidean ℓ₂
- Approximation guarantee
- γ = 1.97 (equivalently δ = 0.97)
- Preprocessing
- Included
- Success guarantee
- Randomized approximation; high-probability success
- timeExponentAtStatedGuarantee
- 1
Assumptions and source notes
The first arXiv abstract states a 1.97-approximate Euclidean search-CVP algorithm from discrete Gaussian sampling. The approximation factor is an entry parameter; this guarantee is not ranked against rows with another factor or a parameter-dependent cost. Exact CVP at the same leading time exponent appears in the later ADS paper.
Source location
Abstract, CVP consequence of discrete Gaussian sampling
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}
}