Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!
FOCS 2015
PublishedSource checked
- Time bound
- 2n + o(n)
- Space bound
- 21 n + o(n)
- Source / version date
- 8 Apr 2015
- Comparison variant
- Exact · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Preprocessing included
- Included
- Target guarantee
- Arbitrary target
- reference
- ADS15
Assumptions and source notes
FOCS 2015. Randomized exact CVP on arbitrary n-dimensional Euclidean lattices and arbitrary targets; total time and space 2^{n+o(n)}.
Selected earlier references
Selected sources cited by this paper.
- Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2015
Identifies the earlier discrete-Gaussian approximation result before the exact 2^n CVP algorithm. Introduction, 1.97-approximate CVP discussion
- Sampling short lattice vectors and the closest lattice vector problem
Miklós Ajtai · Ravi Kumar · D. Sivakumar · 2002
Traces the first randomized near-exact CVP approximation algorithm. Introduction and references [AKS02]
- Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2015
Extends centered Gaussian-combining techniques to shifted distributions with a distance-relative cutoff. Abstract; §4
BibTeXDownload .bib
@misc{paper-eb07a87a7ce7,
author = {Divesh Aggarwal and Daniel Dadush and Noah Stephens-Davidowitz},
title = {{Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!}},
year = {2015},
url = {https://arxiv.org/abs/1504.01995},
cr_date = {2015-04-08},
cr_status = {published},
cr_venue = {FOCS 2015},
cr_author_ids = {divesh-aggarwal; daniel-dadush; noah-stephens-davidowitz},
howpublished = {FOCS 2015; arXiv:1504.01995}
}