2015

# Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing

## Publication

### Publication

*Presented at the ACM-SIAM Symposium on Discrete Algorithms*

Improving on the Voronoi cell based techniques of [28, 24],
we give a Las Vegas eO
(2n) expected time and space algo-
rithm for CVPP (the preprocessing version of the Closest
Vector Problem, CVP). This improves on the eO
(4n) deter-
ministic runtime of the Micciancio Voulgaris algorithm [24]
(henceforth MV) for CVPP 1 at the cost of a polynomial
amount of randomness (which only aects runtime, not cor-
rectness).
As in MV, our algorithm proceeds by computing a short
path on the Voronoi graph of the lattice, where lattice
points are adjacent if their Voronoi cells share a common
facet, from the origin to a closest lattice vector. 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 eO
(2n) 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.
As a byproduct of our work, we also give an optimal
relationship between geometric and path distance on the
Voronoi graph, which we believe to be of independent
interest.

Additional Metadata | |
---|---|

ACM-SIAM Symposium on Discrete Algorithms | |

Organisation | Networks and Optimization |

Dadush, D., & Bonifas, N. (2015). Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms 2015 (SODA) (pp. 295–314). |