CVP / Constant approximation · arbitrary norm

Approximate CVP in time 2^(0.802 n) -- now in any norm!

Thomas Rothvoss · Moritz Venzin

IPCO 2022

PublishedSource checked

Time bound: 2^{(0.802 + ε)n}, for every fixed ε > 0
Space bound: 2^{(0.401 + ε)n}

Source / version date: 5 Oct 2021
Comparison variant: Constant approximation · arbitrary norm
Cost scale: 2^{(c + ε) n}, any fixed ε > 0
Norm: Any norm from a centrally symmetric convex body
Approximation guarantee: γ_ε = O_ε(1)
Preprocessing: Included
Success guarantee: Randomized approximation
model: Norm-oracle/convex-body representation as in §2; polynomial encoding and precision factors suppressed

Assumptions and source notes

Theorem 3.3 extends constant-factor approximate CVP to any norm and rank-n lattice. The approximation constant depends on ε. Lemma 3.1 removes the full-rank restriction with a controlled approximation loss.

Source location

Theorem 3.3; Lemma 3.1; §2 representation conventions
Version: arXiv:2110.02387v1, 5 October 2021

Selected earlier references

Selected sources cited by this paper.

Approximate CVP_p in time 2^(0.802 n)
Friedrich Eisenbrand · Moritz Venzin · 2020
Extends the ℓp constant-factor approach to arbitrary norms. Introduction and §3, reference [EV20]
Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
Uses Kannan’s embedding to turn a closest-vector instance into a higher-dimensional lattice. Proof of Theorem 3.3, reference [Kan87]

Primary source ↗

BibTeXDownload .bib

@inproceedings{rothvoss-venzin-2021,
  author = {Thomas Rothvoss and Moritz Venzin},
  title = {{Approximate CVP in time 2^(0.802 n) -- now in any norm!}},
  year = {2022},
  url = {https://arxiv.org/abs/2110.02387},
  keywords = {CVP, lattice algorithms},
  cr_date = {2021-10-05},
  cr_status = {published},
  cr_venue = {IPCO 2022},
  cr_author_ids = {thomas-rothvoss; moritz-venzin},
  howpublished = {IPCO 2022}
}