Correctness of AKS algorithm for shortest vector problem

Question

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$.

Answer 1

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.