CVP / Approximate decision · polynomial advice

Lattice Problems in NP ∩ coNP

Dorit Aharonov · Oded Regev

Journal of the ACM 2005

PublishedSource checked

Time bound: poly(input size) query time; degree may depend on c
Space bound: poly(input size) advice; degree may depend on c

Source / version date: 8 Sept 2005
Comparison variant: Approximate decision · polynomial advice
Cost scale: Gap factor γ(n); polynomial query time
Norm: Euclidean ℓ₂
Approximation guarantee: c√(n/log n), for every fixed c > 0
Preprocessing: Unbounded; lattice-only advice
advice: N = poly(n) dual-lattice vectors; degree depends on c
Success guarantee: Polynomial-time gap decision from suitable fixed advice

Assumptions and source notes

Theorem 1.4 gives a polynomial query algorithm for GapCVPP with factor c√(n/log n) for every fixed c > 0. Section 5 computes an estimator using polynomially many preprocessed dual-lattice vectors.

Source location

Theorem 1.4 and §5 proof
Version: Author manuscript dated 8 September 2005; JACM 52(5), 2005

Selected earlier references

Selected sources cited by this paper.

Improved Inapproximability of Lattice and Coding Problems with Preprocessing
Oded Regev · 2004
Improves the polynomial-query approximate-decision CVPP factor. §1.3 and Theorem 1.4; reference [26]

Primary source ↗

BibTeXDownload .bib

@article{aharonov-regev-2005,
  author = {Dorit Aharonov and Oded Regev},
  title = {{Lattice Problems in NP ∩ coNP}},
  year = {2005},
  doi = {10.1145/1089023.1089025},
  url = {https://cims.nyu.edu/~regev/papers/cvpconp.pdf},
  keywords = {CVP, lattice algorithms},
  cr_date = {2005-09-08},
  cr_status = {published},
  cr_venue = {Journal of the ACM},
  cr_author_ids = {dorit-aharonov; oded-regev},
  howpublished = {Journal of the ACM}
}