Author: Daniele Micciancio
ACM-SIAM Symposium on Discrete Algorithms - SODA 2008, San Francisco, CA, USA (January 2008). To appear.
Abstract: We give various deterministic polynomial time reductions among approximation problems on point lattices. Our reductions are both efficient and robust, in the sense that they preserve the rank of the lattice and approximation factor achieved. Our main result shows that for any g >= 1, approximating all the successive minima of a lattice (and, in particular, approximately solving the Shortest Independent Vectors Problem, SIVP_g) within a factor g reduces under deterministic polynomial time rank-preserving reductions to approximating the Closest Vector Problem (CVP) within the same factor g. This solves an open problem posed by Blomer in (ICALP 2000). As an application, we obtain faster algorithms for the exact solution of SIVP that run in time n! s^{O(1)} (where n is the rank of the lattice, and s the size of the input,) improving on the best previously known solution of Blomer (ICALP 2000) by a factor 3^n. We also show that SIVP, CVP and many other lattice problems are equivalent in their exact version under deterministic polynomial time rank-preserving reductions.