On the Closest Vector Problem with a Distance Guarantee
CCC 2014
- Time bound
- poly(input size) query time
- Space bound
- O(n) advice vectors
- Source / version date
- 29 Sept 2014
- Comparison variant
- Approximate search · polynomial advice
- Cost scale
- Approximation guarantee γ(n); polynomial query time
- Norm
- Euclidean ℓ₂
- Approximation guarantee
- O(n)
- Preprocessing
- Unbounded; lattice-only advice
- advice
- O(n) vectors; bit precision follows the input-size convention
- Success guarantee
- Approximate lattice-vector search
Assumptions and source notes
A second advice–approximation tradeoff uses only linearly many preprocessing vectors and obtains an O(n) search approximation.
Source location
Abstract; full paper Theorem 5.2 and §1.1 discussion
Version: arXiv:1409.8063v1, 29 September 2014
Selected earlier references
Selected sources cited by this paper.
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
Jeffrey C. Lagarias · Hendrik W. Lenstra, Jr. · Claus-Peter Schnorr · 1990
Uses the O(n^{3/2}) search approximation as its historical benchmark. §1, previous best search-CVPP approximation [LLS90]
- Improved Inapproximability of Lattice and Coding Problems with Preprocessing
Oded Regev · 2004
Separates the earlier decision approximation from search CVPP. §1, decision-CVPP history [Reg04]
- Lattice Problems in NP ∩ coNP
Dorit Aharonov · Oded Regev · 2005
Uses the decision-estimator lineage for the gradient-based search algorithm. §1 and periodic Gaussian discussion [AR05]
- Minkowski’s convex body theorem and integer programming
Ravi Kannan · 1987
Credits projection to a lattice with a close target as a reduction idea. Abstract; §1.1 and §5, reference [Kan87]
- On Bounded Distance Decoding for General Lattices
Yi-Kai Liu · Vadim Lyubashevsky · Daniele Micciancio · 2006
Improves the preprocessed hill-climbing decoder, its radius and the size of the dual-Gaussian advice. Abstract and §1.1; §3
- Lattice Problems in NP ∩ coNP
Dorit Aharonov · Oded Regev · 2005
Explains the predecessor periodic-Gaussian distance estimator and its dual-sampling representation. §1 introduction, Eq. (2)–(3)
@inproceedings{dadush-regev-stephens-davidowitz-2014,
author = {Daniel Dadush and Oded Regev and Noah Stephens-Davidowitz},
title = {{On the Closest Vector Problem with a Distance Guarantee}},
booktitle = {CCC 2014},
year = {2014},
url = {https://arxiv.org/abs/1409.8063},
keywords = {BDD, CVPP, preprocessing, distance guarantee},
cr_date = {2014-09-29},
cr_status = {published},
cr_venue = {CCC 2014},
cr_author_ids = {daniel-dadush; oded-regev; noah-stephens-davidowitz}
}