Approximate CVP_p in time 2^(0.802 n)
ESA 2020
- Time bound
- 2(0.802 + ε)n, for every fixed ε > 0
- Space bound
- 2(0.401 + ε)n
- Source / version date
- 16 Jun 2020
- Comparison variant
- Constant approximation · ℓp norms
- Cost scale
- 2(c + ε) n, any fixed ε > 0
- Norm
- Any fixed ℓp, 1 ≤ p ≤ ∞; full-rank L ⊂ R^n
- Approximation guarantee
- γ(p,ε) = O_{p,ε}(1); not a fixed 1.97 or exact guarantee
- Preprocessing
- Included
- Success guarantee
- Constant probability, amplifiable
- model
- Classical randomized list sieve; polynomial input-size factors suppressed
Assumptions and source notes
Theorem 3.2 covers p ≥ 2; §4 extends the result to 1 ≤ p < 2. For each time slack ε the guarantee uses a constant approximation factor depending on ε. The general-ℓp result is dated to v2; v1 on 11 May covered ℓ∞.
Source location
Theorem 3.2; §4 for p < 2; §1 ambient-dimension discussion
Version: arXiv:2005.04957v2, 16 June 2020
Selected earlier references
Selected sources cited by this paper.
- Sampling short lattice vectors and the closest lattice vector problem
Miklós Ajtai · Ravi Kumar · D. Sivakumar · 2002
Identifies the earlier parameterized near-exact Euclidean CVP approximation. §1, approximation history, reference [AKS02]
- Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
Traces the superexponential enumeration bound before sieving and Voronoi algorithms. §1, historical complexity discussion, reference [Kan87]
- A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
Daniele Micciancio · Panagiotis Voulgaris · 2013
Distinguishes the earlier exact Euclidean Voronoi algorithm from general-norm approximation. §1, exact Euclidean algorithms, reference [MV10a]
- Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian Sampling
Divesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-Davidowitz · 2015
Places the discrete-Gaussian Euclidean algorithm in its complexity comparison. §1, discrete-Gaussian algorithm history, reference [ADRS15]
- Solving the Closest Vector Problem in 2^n Time---The Discrete Gaussian Strikes Again!
Divesh Aggarwal · Daniel Dadush · Noah Stephens-Davidowitz · 2015
Uses exact Euclidean CVP as a comparison point for the broader norm-family approximation. §1, fastest exact Euclidean CVP, reference [ADS15]
@inproceedings{eisenbrand-venzin-2020,
author = {Friedrich Eisenbrand and Moritz Venzin},
title = {{Approximate CVP_p in time 2^(0.802 n)}},
year = {2020},
doi = {10.4230/LIPIcs.ESA.2020.43},
url = {https://arxiv.org/abs/2005.04957},
keywords = {CVP, lattice algorithms},
cr_date = {2020-06-16},
cr_status = {published},
cr_venue = {ESA 2020},
cr_author_ids = {friedrich-eisenbrand; moritz-venzin},
howpublished = {ESA 2020}
}