Thursday, August 16, 2012

Closest vectors

I haven't written about the latest development yet: closest vectors in lattices. This is done using the algorithm in the paper "A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations" by Daniele Micciancio and Panagiotis Voulgaris. As the title suggests, it uses the Voronoi cell V. The idea is

  1. to deal with the special case where the target vector is in 2V, and
  2. to solve the general problem with polynomially many calls to this special case.
See the paper (esp. Algorithm 1) for the details.

Currently, I am working on polishing up documentation, and maybe we still need to change the class structure a little.

1 comment: