CVP / CVP with preprocessing · query cost

Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing

Daniel Dadush · Nicolas Bonifas

SODA 2015

PublishedSource checked

Time bound: Õ(2ⁿ) expected query time
Space bound: Õ(2ⁿ) stored advice and space

Source / version date: 18 Dec 2014
Comparison variant: CVP with preprocessing · query cost
Cost scale: 2^{c n + o(n)}
norm: Euclidean ℓ₂
preprocessing: VR list supplied; Õ(4^n) construction available
advice: All Voronoi-relevant vectors, at most 2(2^n−1)
target: Arbitrary target
success: Las Vegas: exact answer, expected running time
model: Randomized arithmetic operations; polynomial dependence on encoded basis and target

Assumptions and source notes

A Las Vegas query algorithm given the Voronoi-relevant vectors, improving the previous Õ(4^n) query bound. The theorem counts polynomially many operations per relevant vector. Generating the advice is separate and may use the Õ(4^n) Voronoi algorithm.

Source location

Abstract; full paper Theorem 8 (CVP with VR advice)
Version: arXiv:1412.6168v1, 18 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
Improves the exact-CVPP query phase given Voronoi-relevant vectors. Abstract and introduction, prior Õ(4^n) query bound

Primary source ↗

BibTeXDownload .bib

@inproceedings{dadush-bonifas-2014,
  author = {Daniel Dadush and Nicolas Bonifas},
  title = {{Short Paths on the Voronoi Graph and the Closest Vector Problem with Preprocessing}},
  year = {2015},
  url = {https://arxiv.org/abs/1412.6168},
  keywords = {CVP, lattice algorithms},
  cr_date = {2014-12-18},
  cr_status = {published},
  cr_venue = {SODA 2015},
  cr_author_ids = {daniel-dadush; nicolas-bonifas},
  howpublished = {SODA 2015}
}