Lattice Algorithms based on Voronoi Cell Computation

The Voronoi cell computation algorithm of

  1. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
    (Micciancio & Voulgaris - SIAM J. Comput. 2013 / STOC 2010) [eccc, slides]

solves the Closest Vector Problem (CVP) (and a number of other related lattice problems, including SVP and SIVP) deterministically using time O(22n)O(2^{2n}) and space O(2n)O(2^n).

The algorithm was the first one to solve CVP in single exponential time 2O(n)2^{O(n)}, improving the previous nO(n)n^{O(n)} upper bound based on enumeration methods. The algorithm of (1) is still the theoretically fastest deterministic algorithm to solve CVP and SVP, but its running time has been improved to O(2n)O(2^n) using randomization by combinatorial algorithms.

The algorithm of (1) is simple enough to be implemented and run in low dimension (say, n<20n<20), but not competitive in practice with other methods based on Sieving or Enumeration techniques, due to its high space complexity and the fact that its actual running time is close to the theoretical worst-case upper bound.

The method of (1) to solve CVP after the Voronoi cell of the lattice has been computed is a variant of an algorithm first proposed in (2). The method is further studied in (3), and it is also related to the method used in (4) to solve CVP in certain lattices with special structure.

  1. Finding the closest lattice point by iterative slicing
    (Sommer, Feder & Shalvi - SIAM J. Disc. Math. 2009)

  2. Short paths on the Voronoi graph and closest vector problem with preprocessing
    (Dadush & Bonifas - SODA 2015)

  3. Finding a closest point in a lattice of Voronoi’s first kind
    (McKilliam, Grant & Clarkson - SIAM J. Disc. Math. 2014)

Non euclidean norms

The algorithm of (1) is specific to the Euclidean norm, but it has been used in

  1. Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
    (Dadush, Peikert & Vempala - FOCS 2011) [arXiv]

  2. Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
    (Dadush & Vempala - SODA 2012) [arXiv]

  3. Near-optimal deterministic algorithms for volume computation via M-ellipsoids
    (Dadush & Vempala - PNAS 2013) [arXiv]

to solve SVP deterministically in time 2O(n)2^{O(n)}-time with respect to any norm, providing a deterministic alternative to SVP sieving algorithms.

Open Problems