CVP / Approximate decision · polynomial advice

Improved Inapproximability of Lattice and Coding Problems with Preprocessing

Oded Regev

IEEE Trans. Information Theory 2004

PublishedSource checked

Time bound: poly(input size) query time
Space bound: Polynomial-size lattice-dependent advice

Source / version date: Sept 2004
Comparison variant: Approximate decision · polynomial advice
Cost scale: Gap factor γ(n); polynomial query time
Norm: Euclidean ℓ₂
Approximation guarantee: Gap factor n
Preprocessing: Unrestricted; depends only on the lattice
advice: Polynomial-size lattice description
Success guarantee: Polynomial-time threshold decision

Assumptions and source notes

Section V explicitly solves Euclidean GAPCVPP_n. This row tracks a gap decision and distance-estimation guarantee; it does not claim an n-approximate lattice-vector finder.

Source location

§II Definition 2.5; §V Upper Bound, GAPCVPP_n
Version: IEEE Transactions on Information Theory 50(9), September 2004

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
Explains the earlier O(n^{3/2}) CVPP approximation from preprocessed bases. §I, reciprocal KZ preprocessing discussion; reference 6

Primary source ↗

BibTeXDownload .bib

@article{regev-2004-cvpp,
  author = {Oded Regev},
  title = {{Improved Inapproximability of Lattice and Coding Problems with Preprocessing}},
  year = {2004},
  doi = {10.1109/TIT.2004.833350},
  url = {https://cims.nyu.edu/~regev/papers/cvpp.pdf},
  keywords = {CVP, lattice algorithms},
  cr_date = {2004-09-30},
  cr_date_precision = {month},
  cr_status = {published},
  cr_venue = {IEEE Transactions on Information Theory},
  cr_author_ids = {oded-regev},
  howpublished = {IEEE Transactions on Information Theory}
}