5
$\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$
1
  • $\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
    Commented Aug 16, 2016 at 22:03

0

Your Answer

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

Browse other questions tagged or ask your own question.