Title: From Euclid to Lenstra-Lenstra-Lovasz: Revisiting Lattice Basis Reduction
Speaker: Phong Nguyen (CNRS/ENS, Paris)

Abstract:
Lattices are simple yet fascinating mathematical objects. Roughly speaking, 
they are linear deformations of the n-dimensional grid Z^n.
Lattices have incredibly many applications in mathematics and computer 
science. Of particular importance is lattice basis reduction,
which is the problem of finding "nice" representations of lattices.
In this talk, we will revisit lattice basis reduction, from Euclid's 
gcd algorithm to the celebrated LLL or L^3  algorithm.
We will discuss in particular two new reduction algorithms:
the greedy algorithm and the L^2 algorithm,
which are somewhat related to old notions of reduction introduced 
by Hermite and Minkowski. Curiously, one can achieve a Euclid-like
complexity for lattice basis reduction: in some sense, one can compute
a  reduced basis (without fast integer arithmetic) in essentially the 
same time as the elementary method to multiply integers.