Daniele Micciancio, University of California, San Diego
                          
Solving all lattice problems in deterministic single exponential time

Abstract:
In this talk we describe  deterministic single exponential time algorithms to
solve all the most important computational problems on point lattices in NP,
including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP),  and
Shortest Independent Vectors Problem (SIVP). This improves the $n^{O(n)}$
running time of the best previously known algorithms for CVP (Kannan, Math.
Operation Research 12(3):415-440, 1987) and SIVP (Micciancio, Proc. of SODA,
2008), and gives a deterministic alternative to the $2^{O(n)}$-time (and space)
randomized algorithm for SVP of (Ajtai, Kumar and Sivakumar, STOC 2001).  The
core of our algorithm is a new method to solve the closest vector problem with
preprocessing (CVPP) that uses the Voronoi cell of the lattice  (described as
intersection of half-spaces) as the result of the preprocessing function. In
the process, we also give algorithms for several other lattice problems,
including computing the kissing number of a lattice, and computing the set of
all Voronoi relevant vectors. All our algorithms are deterministic, and have
$2^{O(n})$ time and space complexity (Talk based on joint work with P.
Voulgaris, STOC 2010)




                      The lecture will take place in the 
                    Seminar Room, Room 261, Ziskind Building
                            on Sunday, July 11, 2010
                                    at 11:00