Speaker: Gorjan Alagic

Day:  Wednesday, 09/21/2005
Room: ITE 336
Time: 3:30pm

Title: The Shortest Vector Problem

Abstract:
We discuss an approximation algorithm for finding the shortest vector in
the integer lattice generated by a basis of n linearly independent vectors
in Q^n. If the basis is orthogonal, it is easy to see that the solution is
just the shortest vector in the basis. In general, however, the problem
seems to be very difficult. The idea behind one of the best known
algorithms, due to A.K. Lenstra, H.W. Lenstra, and L. Lovasz, is to find a
'nearly' orthogonal basis. This algorithm can be viewed as a natural
extension of Euclid's and Gauss' algorithms, which can be used to
efficiently solve the problem exactly in one and two dimensions,
respectively. The LLL algorithm runs in polynomial time and has an
exponential approximation factor. No polynomial approximation factor
algorithm is known.