TITLE: Lattice Algorithms: State of the Art and Open Problems
SPEAKER: Daniele Micciancio (UCSD)

ABSTRACT
Computational problems on point lattices play an important role in
many areas of computer science and mathematics. Since the discovery of
the LLL basis reduction algorithm in the early '80s, much effort has
gone into the development of better (faster, or more accurate)
algorithms, largely motivated by applications in cryptanalysis. Today,
with the flourishing of lattice based cryptography (i.e.,
cryptographic function whose security rests on the computational
intractability of lattice problems, including the recent development
of fully homomorphic encryption schemes), improving our understanding
of the effort required to solve lattice problems has never been more
important, as it plays a critical role determining appropriate key
sizes. In this talk I will describe the current state of the art in
lattice algorithms, including the asymptotically fastest known
algorithm of Micciancio and Voulgaris, as well as less understood but
practically effective heuristics, and a panoramic of the many research
problems that are still open in the area.

Bio sketch: Daniele Micciancio got his PhD from MIT in 1998, and
joined the UCSD CSE faculty in 1999. He is the recipient of several
awards, including an NSF CAREER award, Sloan Fellowship and Hellman
Fellowship. He is most known for his research on the complexity of
lattice problems, which spans the whole spectrum from computational
complexity and algorithms, to cryptography. His most notable
achievements include the first significant inapproximability result
for the Shortest Vector Problem, pioneering the use of cyclic and
ideal lattices from algebraic number theory for the construction of
very efficient cryptographic primitives based on worst-case complexity
assumptions, and the discovery of the first single exponential time
algorithm to solve all the most important computational problems on
point lattices.