On the Closest Vector Problem with a Distance Guarantee
CCC 2014
- Time bound
- 2(log2(e) alpha2/(1-2alpha)2)n+o(n) per query
- Space bound
- 2(log2(e) alpha2/(1-2alpha)2)n+o(n) advice
- Source / version date
- 29 Sept 2014
- Comparison variant
- Classical · preprocessing/radius tradeoffs
- Cost scale
- Parameterized query time
- Decoding radius
- dist(t,L) <= alpha lambda_1(L)
- Preprocessing time
- Unbounded; source counts advice rather than its construction time
- Advice / space
- N=O(alpha^2 n^2/(1-2alpha)^2 * exp(alpha^2 n/(1-2alpha)^2 + 4/(1-2alpha))) vectors
- Parameter domain
- Any fixed 0 < alpha < 1/2; exact corollary allows Omega(1/sqrt(n)) < alpha < 1/2
- Success guarantee
- Advice can be chosen to decode every promised target
- quarterRadiusExample
- alpha=1/4: query time and advice exp(n/4+o(n)) = 2^{(log₂(e)/4)n+o(n)}, coefficient ≈0.36067376022224085
- model
- Classical; query time after unbounded target-independent preprocessing
Assumptions and source notes
For fixed alpha, suppressing polynomial factors gives this expression from Corollary 3.3. The first arXiv abstract already states N≈Õ(n exp(alpha²n/(1−2alpha)²)) advice vectors and Õ(nN) query time. At alpha=1/4 this specializes to exp(n/4+o(n)) time and advice, or base-2 coefficient log₂(e)/4≈0.3606737602. This example is part of the same tradeoff rather than a separate result or category. All costs here are per query or stored advice after unbounded target-independent preprocessing.
Source location
Corollary 3.3, printed pp. 14–15; original v1 abstract includes the formula, alpha=1/4 is a direct substitution
Version: 2014 author manuscript / arXiv:1409.8063; first arXiv date
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}
}