Type: Seminar

Distribution: World

Expiry: 18 Jan 2007

Auth: billu@galois.maths.usyd.edu.au

Speaker: Damien Stehle Title: Lattice Point Enumeration Revisited Time & Place: 3-4pm, Thursday 18 January, Carslaw 535 Abstract: Lattice point enumeration is the basis of the best known algorithm to solve exactly the shortest vector problem. This is also the time-consuming part of Schnorr’s block-based lattice reductions, that are very famous in the cryptography community. This enumeration algorithm, known as Fincke-Pohst algorithm for number theorists and Kannan’s algorithm for cryptographers, has a d^{d/2 +o(d)} complexity, where d is the lattice dimension. This upper bound was proved by Hellfrich more than 20 years ago. In this talk, I will show that this analysis is far from being tight, and describe the proof of an improved upper bound.

Calendar (ICS file) download, for import into your favourite calendar application

UNCLUTTER for printing

AUTHENTICATE to mark the scnews item as read