Closest Vector Problem
Find the lattice point closest to a target.
Exact · general ℓp norms
Exact search CVP for every fixed 1 < p < ∞, target in the lattice span
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Solving the Closest Vector Problem with respect to ℓp NormsarXiv 1104.3720SourceBibTeX / detailsℓp norms exact polynomial space | 12 Jul 2011 | poly(p, log r) · n(2 + o(1))n arithmetic operations | Polynomial in the encoded input size | PreprintSource checked |
| 2 | Solving the Closest Vector Problem with respect to ℓp NormsarXiv 1104.3720SourceBibTeX / detailsℓp norms exact arithmetic model | 16 May 2011 | poly(p, log r) · n(5/2 + o(1))n arithmetic operations | No polynomial-space guarantee asserted for this version | PreprintSource checked |
Comparison definition & assumptions
- Regime
- Exact search CVP for every fixed 1 < p < ∞, target in the lattice span
- Computation
- Classical
- Rigor
- Provable
- Instances
- Worst case
- Cost scale
- n^{c n + o(n)} arithmetic operations
- Parameter
- n
- Description
- Exact CVP for the family of ℓp norms, with arithmetic operation counts and space guarantees stated per source version.
- Comparison rules
- For each fixed 1 < p < ∞ return a closest vector in an arbitrary full-rank rational n-dimensional lattice under ℓp distance. The target lies in the span of the lattice. Count arithmetic operations, with polynomial input-size factors separated. Preserve p-dependence and bit-size/space guarantees. Euclidean-only algorithms do not solve this whole norm-family contract.
- Tags
- ℓp norms, exact, arithmetic model