show/hide this revision's text 2 corrected wording

A lattice L is the image of ℤn ⊂ ℝn under the action of a matrix A ∈ GL(ℝn). The rank of L is the dimension n of the space it lives in.

  • The closest vector problem (CVP) asks, for a vector x ∈ ℝn, whether the closest element of L is "close" to x (distance at most 1 in the Euclidean norm) or not.
  • The shortest vector problem (SVP) asks whether the shortest non-zero element of L is "short" (has length at most 1) or not.

Both problems are NP-complete. There is an active research programme on finding efficiently solvable approximation versions, which may be interpreted as problems where you are promised that there is a constant-factor an approximation-factor gap f(n) between YES instances and NO instances. This introduces the promise problem-families

  • GapCVPf(n) 
    --- asks whether the closest vector in L to x is "close" (distance at most 1 away) or "far" (distance at least f(n) away), given that at least one of these is true;

  • GapSVPf(n) 
    --- asks whether the shortest non-zero vector in L is "short" (length at most 1) or "long" (length at least f(n)), given that at least one of these is true.

The paper "Lattice problems in NP ∩ coNP" shows that the approximation problems GapCVP√n and GapSVP√n are both in (as you might guess) NP ∩ coNP; furthermore, the witnesses for both YES and NO instances can in principle be generated from a particular probability distribution, and so are in some sense plentiful for this approximation factor.
show/hide this revision's text 1 [made Community Wiki]

A lattice L is the image of ℤn ⊂ ℝn under the action of a matrix A ∈ GL(ℝn). The rank of L is the dimension n of the space it lives in.

  • The closest vector problem (CVP) asks, for a vector x ∈ ℝn, whether the closest element of L is "close" to x (distance at most 1 in the Euclidean norm) or not.
  • The shortest vector problem (SVP) asks whether the shortest non-zero element of L is "short" (has length at most 1) or not.

Both problems are NP-complete. There is an active research programme on finding efficiently solvable approximation versions, which may be interpreted as problems where you are promised that there is a constant-factor gap f(n) between YES instances and NO instances. This introduces the promise problem-families

  • GapCVPf(n) 
    --- asks whether the closest vector in L to x is "close" (distance at most 1 away) or "far" (distance at least f(n) away), given that at least one of these is true;

  • GapSVPf(n) 
    --- asks whether the shortest non-zero vector in L is "short" (length at most 1) or "long" (length at least f(n)), given that at least one of these is true.

The paper "Lattice problems in NP ∩ coNP" shows that the approximation problems GapCVP√n and GapSVP√n are both in (as you might guess) NP ∩ coNP; furthermore, the witnesses for both YES and NO instances can in principle be generated from a particular probability distribution, and so are in some sense plentiful for this approximation factor.