Closest Vector Problem
Find the lattice point closest to a target.
Exact · polyhedral norms
Exact search CVP for rational polyhedral norms, 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 / detailspolyhedral norms exact arithmetic model | 16 May 2011 | (s log r)O(1) · n(2 + o(1))n arithmetic operations | Polynomial space explicitly established in the 12 July v3 refinement | PreprintSource checked |
Comparison definition & assumptions
- Regime
- Exact search CVP for rational polyhedral norms, 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 a norm ball described by rational linear inequalities; the input-size factor includes its constraints.
- Comparison rules
- Given a rational centrally symmetric full-dimensional polytope with s inequalities, a rational full-rank lattice and a target in its span, return a closest vector in the induced norm. Count arithmetic operations; keep the polynomial factor in s and the coefficient bit length explicit. This is a polyhedral-norm guarantee, not a result for an arbitrary oracle norm.
- Tags
- polyhedral norms, exact, arithmetic model