2
$\begingroup$

I am confused on the definition of GAP SVP. The problem states that for a fixed $\gamma \geq 1$, given a basis $B$ of a lattice and a $d>0$, GAPSVP asks to determine if $\lambda\leq d$ or $\lambda > \gamma d$. My confusion is that what if $d<\lambda\leq \gamma d$? What would be the answer of GAP SVP then? I read from Micciancio's Fall 2021 CSE206A notes that any answer is acceptable in that case but what does that even mean?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

Micciancio's notes are correct, and the standard way of explaining things, so let's elaborate some.

First, its worth mentioning this has nothing to do with (Gap)SVP specifically, and everything to do with what are called promise problems more generally.

A promise problem is a certain relaxation of a standard decision problem. They are meant to relax the notion of correctness for the problem. The standard notion of correctness can be summarized "The algorithm is correct on all inputs". There are two natural relaxations of this

  1. Randomized classes (like BPP, ZPP, (co)RP). On any particular instance, the algorithm now only needs to be right " on average", where you average over internal choices of random coins.

  2. Promise problems, where you are fine with the algorithm making mistakes on "hard instances", but it always has to be right on "easy instances".

In particular, on hard instances, an algorithm can be completely incorrect, and we don't care. As long as it is right on easy instances, we say its right overall.

To bring things back to GapSVP, the hard instances are when $d\leq \lambda\leq \gamma d$. So we say an algorithm solves GapSVP if

  1. Given an instance $(L, d)$ (a lattice, and distance bound) that is easy, meaning $\lambda_1(L)\leq d$ or $\lambda_1(L)\geq \gamma d$, the algorithm returns the right answer

  2. Given a hard instance, the algorithm returns whatever it wants. We don't care.

In particular, given the same hard instance twice, an algorithm could return both answers (it doesn't have to be internally consistent). We don't care --- we only care how the algorithm does on "easy" instances, measured by $\gamma$.

$\endgroup$
1
  • 4
    $\begingroup$ This is a very good answer, but I would not use the terms “hard/easy instances” for the concept you’re discussing, because they usually mean something entirely different. We more often say that instances “satisfy the promise,” otherwise they are “gap instances.” $\endgroup$ Apr 11, 2022 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.