Colloquium Details
A Tour of High-dimensional Geometry in Computer Science
Speaker: Oded Regev, Tel Aviv University and CNRS, ENS, Paris
Location: Warren Weaver Hall 1302
Date: March 9, 2012, 11:30 a.m.
Host: Denis Zorin
Synopsis:
High-dimensional geometry has played a key role in computer science since its early days, with the ellipsoid method for convex optimization and the LLL algorithm being two notable examples. In this talk we will present some more recent results on the interface between these two fields, including strong bounds in communication complexity, quantum computation, attacks on cryptographic signature schemes, and constructions of provably secure lattice-based cryptographic schemes. Special emphasis will be given to the latter topic, and especially to the development of the Learning with Errors (LWE) problem and its applications.
Speaker Bio:
Oded Regev is a professor in Tel Aviv University and a directeur de recherche in the École Normale Supérieure, Paris under the CNRS. He received his Ph.D. in Computer Science from Tel Aviv University in 2001. He is the recipient of the Krill Prize for Excellence, awarded by the Wolf foundation in 2005, as well as best paper awards in STOC'03 and Eurocrypt'06. He was awarded a European Research Council (ERC) Starting Grant in 2008. His main research areas include theoretical computer science, cryptography, quantum computation, and complexity theory. A main focus of his research is in the area of lattice-based cryptography, where he introduced several key concepts, including the "learning with error" problem and the use of Gaussian measures.
Notes:
In-person attendance only available to those with active NYU ID cards.