5
$\begingroup$

Short question

In the end of section 1 of Regev's notes about the AKS algorithm for SVP, why is the following true?

for each such $i$,$y_i− x_i$ remains $w$ with probability $1/2$ or otherwise becomes one of $w+v$ or $w−v$.

Extended question

AKS finds a shortest non-zero vector of any $n$-dimensional Euclidean lattice $\Lambda$ in time $2^{O(n)}$.

Actually, it is a randomized algorithm and the output is correct with very high probability, say $1 - 2^{\Omega(n)}$.

Although the intuition about why the output is correct with high probability is simple, the proof is rather technical and it basically goes like this:

The algorithm samples a set of vectors $x_1, ..., x_N$ in the beginning. To each of those vectors, one lattice point is associated (the number of lattice points is much smaller than $N$, so a lot of $x_i$ maps to same lattice point). To prove that the algorithm works (with overwhelming probability) you substitute the sampling method so that if $x_i$ is in a specific region $C_1$, then it is replaced by $x_i + v$, if it it lies in another specific (symmetric) region $C_2$, then it is replaced by $x_i - v$, or it continues to be $x_i$ otherwise, where $v$ is a shortest vector.

Then, the goal is to show that for at least one pair of vectors $x_i$ and $x_j$ that map to a same $w \in \Lambda$, we have $x_i \in C_1 \cup C_2$ and $x_j \not \in C_1 \cup C_2$, so that the difference of the associated lattice points become $(w \pm v) - w = \pm v$, which is a shortest vector.

But I don't understand the analysis of the probabilities involved in this step. Since the vectors $x_i$ considered in the end of section 1 of Regev's notes are all points in $C_1 \cup C_2$, all of them should be "flipped" around $v$, then $w$ would never remain $w$.

$\endgroup$
  • $\begingroup$ Each vector is tossed independently, so, on average, half the vectors $x_i$ will flip from $C_1$ to $C_2$, or vice versa, an the other half will stay put. Does that answer your question? $\endgroup$ – Sasho Nikolov Jun 9 at 21:13
  • $\begingroup$ No really... Because at this part of the notes, Regev is referring only to the "green" points, that is, points that are already in $C_1 \cup C_2$, and all those points must be flipped (by the definition of the function $\tau$). And even if we considered all points instead of only the green ones, the probability that it is not flipped should be $\frac{Vol(B(0,2) \setminus C_1 \cup C_2)}{Vol(B(0,2))}$, shouldn't it? $\endgroup$ – Hilder Vítor Lima Pereira Jun 10 at 8:13
  • 1
    $\begingroup$ It's not true that all gree points are flipped. He says "After choosing each $x_i$, we toss a fair coin and if it comes up heads, we replace $x_i$ with $\tau(x_i)$". Think of every point $x_i$ as having a coin attached to it. Before you use $x_i$, you toss the coin to decide whether to keep $x_i$ as $x_i$ or to replace it by $\tau(x_i)$. This is done independently for each $x_i$. $\endgroup$ – Sasho Nikolov Jun 10 at 17:00
  • $\begingroup$ Oh, I see. So I misread it. Thank you very much for your comments. If you want to turn it into an answer, feel free to do so. Now what is puzzling me is the fact that if we play differently with the tossing probability (for instance, applying $\tau$ to all $x_i$), then the distribution of $x_i$ is still uniform, but the correctness of the algorithm is no longer guaranteed. Hence, the number of sampled points $x_i$ and their distribution are not enough to prove correctness and therefore it depends on something not controlled by the algorithm (the way we toss the points in the analysis)... $\endgroup$ – Hilder Vítor Lima Pereira Jun 11 at 6:44
5
$\begingroup$

What you seem to be missing is that $\tau$ is not applied to all "green" vectors. Instead, think of every point $x_i$ as having a coin attached to it. Before you use $x_i$ in the algorithm, you toss the coin to decide whether to keep $x_i$ as $x_i$ or to replace it by $\tau(x_i)$. This is done independently for each $x_i$, so, with very high probability, the fraction of green vectors that $\tau$ is applied to will be very close to $\frac12$.

I have always found this analysis mysterious, but let me try to give some intuition. I think the analysis tries to exploit the fact that the sieving step only uses $y_i$, and $y_i$ does not distinguish between $x_i$ and $x_i\pm v$ for any lattice vector $v$. Since the sieving step does not need this information, you can think of the analysis as "hiding" from the algorithm which point in the pair $\{x_i, \tau(x_i)\}$ was actually sampled, until the algorithm absolutely must know this information. This is sometimes called the principle of deferred decisions. With this trick, you can argue that there are many possible random choices that would've led to the same set of points surviving to step 3 of the algorithm, and then you argue that at step 3 many of these random choices lead to a correct output. On the other hand, if you applied $\tau$ to every point, then you wouldn't "hide" anything from the algorithm, i.e. you wouldn't be taking advantage of the fact that there is randomness that's not used by the sieving step 2, and is "free" to be used at step 3.

$\endgroup$
  • $\begingroup$ Do you think that it is really important for that analysis that some points are flipped only at the end? $\endgroup$ – Hilder Vítor Lima Pereira Jun 12 at 6:02
  • $\begingroup$ It seems essential for the analysis as far as i can tell. $\endgroup$ – Sasho Nikolov Jun 15 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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