How to find the closest point given the Voronoi relevant vectors?

Question

Let M be the generator matrix of a $N\times N$ lattice, and $\tilde{N}$ the set of Voronoi relevant vectors. The Voronoi cell for the origin can be written as $\text{Vor}_{\bf 0}(M)=\left\{{\bf x}: |{\bf x}|\leq|{\bf x-c}|\text{ for } \forall {\bf c}\in \tilde{N}\right\}$. My question is given $\tilde{N}$, how to find the closest lattice vector for a given point ${\bf x}\in R^N$? Equivalently, given $\tilde{N}$, how to translate the given point ${\bf x}$ back to $\text{Vor}_{\bf 0}$?

If $\tilde{N}$ is not given, the closest point can be found with the algorithm introduced here, and the same algorithm can be modified to find $\tilde{N}$. The motivation for my question is that I would like to find the closest points for a large number of ${\bf x}$'s, for the same lattice. Running the closest point search algorithm is very expensive, hence I am hoping to use relevant vectors to find the closest points.

This is my attempt to translate a given point ${\bf x}$ back to $\text{Vor}_{\bf 0}$ given the relevant vectors $\tilde{N}$

for c in $\tilde{N}$
    overlap = x^T * c/norm(c)^2 
    if abs(overlap) > 1/2
        x = x - round(overlap) * c
    end
end

which seems working for 2D lattices, but not for 3D lattices. Hence I am not sure if the algorithm is correct, or if it is possible to do that for general lattices.

Answer 1

I believe state of the art for this is Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing by Bonifas and Dadush. For instance, see the following quote from the abstract

Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice - the lattice vectors inducing facets of the Voronoi cell - as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the $\tilde{O}(4^n)$ path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors.

This is to say that Bonifas+Dadush should imply a (randomized) algorithm of complexity $O(\mathsf{poly}(N)|\tilde{N}|)$ (as a side note, using $N$ for a dimension and $\tilde{N}$ for a set is perhaps not the best choice of notation). Note that this may not mean efficient, as $|\tilde{N}|$ can grow exponentially in $N$. But, if you have a lattice for which you know that $|\tilde{N}|$ is small, it should efficiently solve your problem.

Note that one can often solve CVP efficiently even in lattices that have exponentially many Voronoi relevant vectors. This is true if they have small extension complexity, see Lifts for Voronoi Cells of Lattices by Schymura, Seidel, and Weltge.

It's also worth mentioning that there have been improvements for finding $\tilde{N}$. In particular, see A Deterministic Single Exponential Time Algorithm for Most Lattice Problems by Micciancio+Voulgaris.