Symbolic Computation Group
David R. Cheriton School of Computer Science


Friday, November 4, 2011 at 1:30pm, at U. of Western Ontario
Abstract: The LLL lattice reduction algorithm of 1982 has proven to be useful in a wide variety of fields. It can be used to approximately solve computationally difficult latticebased problems, such as the shortest vector problem, in polynomial time. We present a new algorithm for lattice reduction which is the first algorithm to have a complexity bound which is both polynomial and quasilinear in the bitlength of the input. To achieve this we present an independently interesting toolkit for analyzing incremental lattice reductions.

Last modified on Sunday, 04 November 2012, at 15:42 hours.