2008-08-29 Wan Daqing: The Shortest Lattice Vector Problem

Speaker: Daqing Wan (University of California, Irvine)

Title: The Shortest Lattice Vector Problem

Time: 2008 Aug 29, Friday 4:00pm-5:00pm

Place: Capital Normal University, Department of Math, Room 210

Abstract: Given a n-dimensional lattice in the m-dimensional
Euclidean space R^m, the shortest lattice vector problem (SVP)
is to find a shortest non-zero lattice vector. This optimization
problem has wide ranging fundamental applications in mathematics,
computer sciences and enginnering. The history of SVP dates back
to Gauss, Dirichlet and Hermite who studied it in the language of
quadratic forms in connection to number theory and diophantine
approximation. Proving the existence of short lattice vectors is
a central problem in geometry of numbers as founded by Minkowski.
The celebrated LLL (Lenstra-Lenstra-Lovasz) algorithm was a major
breakthrough in solving SVP. The SVP is currently one of the most
active and intensively studied topics in mathematics and
computer sciences.

In this expository lecture, we shall give an overview of the
developments on the SVP, as well as its connections to
computational complexity (NP-hard problems) and cryptography,
focusing more on recent progresses.