4
$\begingroup$

Babai's nearest plane algorithm solves approximate-CVP (Closest Vector Problem) where the approximation factor is $2(\frac{2}{\sqrt{3}})^n$.

Let $b_1,...,b_n$ be a basis and $t$ be the target. This algorithm finds an integer $c$ such that the hyperplane $c b_n^*+span(b_1,...,b_{n-1})$ is close to $t$. Recursively, it finds a lattice point $x^\prime \in L(b_1,...,b_{n-1})$ that is closest to the projection $t^\prime$ of $t-cb_n$ onto $span(b_1,....,b_{n-1})$ and output $x=x^\prime+cb_n$.

In proof, we have $$||x-t|| \le 2(\frac{2}{\sqrt{3}})^n||y-t||$$ where y is the nearest point to $t$.

If $||t-y|| \le \frac{b_n^*}{2}$ then $y \in c b_n^*+span(b_1,...,b_{n-1})$ and $y^\prime =y-cb_n \in L(b_1,....,b_n)$ is the nearest point to $t^\prime$. I could not understand how $x^\prime$ is within the distance $2(\frac{2}{\sqrt{3}})^{n-1}||t^\prime-y^\prime||$ and how to prove in this case.

$\endgroup$
  • $\begingroup$ I don't have time to sketch the entire proof, but an important step of Babai's algorithm is to $\delta$-LLL reduce the basis. The properties of an LLL-reduced basis are integral to the proof. This should help: cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/cvp.pdf $\endgroup$ – bkjvbx Aug 16 '16 at 22:03

Your Answer

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

Browse other questions tagged or ask your own question.