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

<p>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 <span class="math-container">$y_i$</span>, and <span class="math-container">$y_i$</span> does not distinguish between <span class="math-container">$x_i$</span> and <span class="math-container">$x_i\pm v$</span> for any lattice vector <span class="math-container">$v$</span>. 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 <span class="math-container">$\{x_i, \tau(x_i)\}$</span> was actually sampled, until the algorithm absolutely must know this information. This is sometimes called the <a href="https://en.wikipedia.org/wiki/Principle_of_deferred_decision" rel="noreferrer"><em>principle of deferred decisions</em></a>. 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 <span class="math-container">$\tau$</span> 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.</p>

CC BY-SA 4.0
2019-06-12T06:02:07.933Z
Do you think that it is really important for that analysis that some points are flipped only at the end?
Hilder Vitor Lima Pereira
CC BY-SA 4.0
2019-06-15T15:20:01.390Z
It seems essential for the analysis as far as i can tell.
Sasho Nikolov
CC BY-SA 4.0
2019-06-12T02:38:15.163Z
2019-06-12T02:38:15.163Z
Sasho Nikolov
<p><strong>Short question</strong></p>

<p>In the end of section 1 of <a href="https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/svpalg.pdf#page=4" rel="noreferrer">Regev's notes</a> about the AKS algorithm for SVP, why is the following true?</p>

<blockquote>
  <p>for each such <span class="math-container">$i$</span>,<span class="math-container">$y_i− x_i$</span> remains <span class="math-container">$w$</span> with probability <span class="math-container">$1/2$</span> or otherwise becomes one of <span class="math-container">$w+v$</span> or <span class="math-container">$w−v$</span>.</p>
</blockquote>

<p><strong>Extended question</strong></p>

<p>AKS finds a shortest non-zero vector of any <span class="math-container">$n$</span>-dimensional <a href="https://en.wikipedia.org/wiki/Lattice_(group)" rel="noreferrer">Euclidean lattice</a> <span class="math-container">$\Lambda$</span> in time <span class="math-container">$2^{O(n)}$</span>. </p>

<p>Actually, it is a randomized algorithm and the output is correct with very high probability, say <span class="math-container">$1 - 2^{\Omega(n)}$</span>.</p>

<p>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: </p>

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

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

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

CC BY-SA 4.0
2019-06-09T21:13:16.227Z
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?
Sasho Nikolov
CC BY-SA 4.0
2019-06-10T08:13:05.883Z
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?
Hilder Vitor Lima Pereira
CC BY-SA 4.0
2019-06-10T17:00:06.340Z
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$.
Sasho Nikolov
CC BY-SA 4.0
2019-06-11T06:44:29.670Z
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)...
Hilder Vitor Lima Pereira
<randomized-algorithms><exp-time-algorithms><integer-lattice><correctness>
Correctness of AKS algorithm for shortest vector problem
Hilder Vitor Lima Pereira
# Correctness of AKS algorithm for shortest vector problem

(Asked by: username_0 on 2019-06-09)

**Short question**

In the end of section 1 of [Regev's notes](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/svpalg.pdf#page=4) 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](https://en.wikipedia.org/wiki/Lattice_(group)) $\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$.

**Tags:** randomized-algorithms, exp-time-algorithms, integer-lattice, correctness

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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?  
> **username_1**: 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$.  
> **username_0**: 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)...  

---

## 1 answers

### Answer by username_1 on 2019-06-12. Score: 6 | Accepted answer

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*](https://en.wikipedia.org/wiki/Principle_of_deferred_decision). 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.

> **Comments:**
> **username_0**: Do you think that it is really important for that analysis that some points are flipped only at the end?  
> **username_1**: It seems essential for the analysis as far as i can tell.  

---

