Covering Convex Bodies and the Closest Vector Problem

Márton Naszódi · Moritz Venzin

Discrete & Computational Geometry 2022

Time bound

2^O(n) (1/δ)^n/2 poly(input size, log(1/δ)), 0<δ<1

Space bound

2ⁿ poly(input size), using the general-norm constant-approximation solver

Source / version date

22 Aug 2019

Comparison variant

Approximate search · Euclidean

Cost scale

Parameterized time bound in n and approximation factor

Norm

Euclidean ℓ₂ (p=2 specialization)

Approximation guarantee

Distance at most (1+δ) dist(t,L), for 0<δ<1

Preprocessing

Included, using a general-norm 2-CVP subroutine; covering generated locally

Success guarantee

Randomized success at least 1-2^{-n}; deterministic net enumeration is also discussed

Assumptions and source notes

The Euclidean specialization p=2 of the smoothness-based covering algorithm improves the dependence on approximation accuracy. This is an alternative algorithmic bound rather than a claim to beat the already known 2^{n+o(n)} exact Euclidean CVP bound. No numerical leading coefficient is inferred from the hidden 2^{O(n)} factor.

Source location

Abstract; §1, item (5); Theorem 4.6, using the ℓ₂ modulus of smoothness with power q=2
Version: arXiv:1908.08384v1, 22 August 2019

Primary source ↗

@article{naszodi-venzin-2019,
  author = {Márton Naszódi and Moritz Venzin},
  title = {{Covering Convex Bodies and the Closest Vector Problem}},
  journal = {Discrete & Computational Geometry},
  year = {2022},
  volume = {67},
  pages = {1191--1210},
  doi = {10.1007/s00454-022-00392-x},
  url = {https://arxiv.org/abs/1908.08384},
  keywords = {CVP, approximation, covering, modulus of smoothness},
  cr_date = {2019-08-22},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {Discrete & Computational Geometry 67 (2022)},
  cr_author_ids = {marton-naszodi; moritz-venzin}
}