Closest Vector Problem
Find the lattice point closest to a target.
14 variants · 25 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
CVPExact · worst caseClassical · ProvableExact Euclidean CVP, arbitrary targetsWorst case21 CVPApproximate search · EuclideanClassical · ProvableApproximate Euclidean search CVP; each result states its factor γ or error parameter δWorst case3— CVPApproximate search · polynomial adviceClassical · ProvableEuclidean search CVPP with polynomial-size lattice-dependent advice and polynomial query timeWorst case3— CVPProvable · polynomial spaceClassical · ProvableExact Euclidean CVP with polynomial workspaceWorst case30.5 CVPApproximate decision · polynomial adviceClassical · ProvableEuclidean GapCVPP with polynomial-size lattice-dependent advice and polynomial query timeWorst case2— CVPCVP with preprocessing · query costClassical · ProvableSeparate lattice-dependent preprocessing from per-target query timeArbitrary targets21 CVPExact · general ℓp normsClassical · ProvableExact search CVP for every fixed 1 < p < ∞, target in the lattice spanWorst case22 CVPHeuristic · classicalClassical · HeuristicExact Euclidean CVP; include all target-dependent workArbitrary lattice; heuristic spherical-list model20.292481 CVPHeuristic · preprocessing query costClassical · HeuristicExact CVPP query time; preprocessing and storage bounded by 2^{n+o(n)}Fixed lattice; arbitrary target20.059 CVPConstant approximation · arbitrary normClassical · ProvableFor every ε > 0, some constant γ_ε approximates search CVP in any normWorst case10.802 CVPConstant approximation · ℓp normsClassical · ProvableFor every ε > 0 and fixed p ∈ [1,∞], some constant γ(p,ε) approximates full-rank CVP_pWorst case10.802 CVPExact · polyhedral normsClassical · ProvableExact search CVP for rational polyhedral norms, target in the lattice spanWorst case12 CVPExact · polynomial-space query · compact basisClassical · ProvableExact Euclidean CVPP with polynomial-space query computation and an explicitly bounded compactness cWorst case; c-compact basis supplied as advice1— CVPCVP · Haar-random latticesClassical · ProvableFix the target model, success probability and whether preprocessing is allowedHaar random0—