2018 Gödel Prize

The 2018 Gödel Prize is awarded to Professor Oded Regev for his paper:

  • On lattices, learning with errors, random linear codes, and cryptography Journal of the ACM, volume 56, issue 6, 2009 (preliminary version in the 37th annual Symposium on Theory of Computing, STOC 2005.)

This year the prize will be awarded at the 45th International Colloquium on Automata, Languages, and Programming to be held during July 9-13, 2018 in Prague, Czech Republic.

Regev’s paper introduced the Learning With Errors (LWE) problem, and proved its average-case hardness assuming the worst-case (quantum) hardness of various well-studied problems on point lattices in Rn. It also gave an LWE-based public-key encryption scheme that is much simpler and more efficient than prior ones having similar worst-case hardness guarantees; this system has served as the foundation for countless subsequent works. Lastly, the paper introduced elegant and powerful techniques, including a beautiful quantum algorithm, for the study of lattice problems in cryptography and computational complexity. Regev’s work has ushered in a revolution in cryptography, in both theory and practice. On the theoretical side, LWE has served as a simple and yet amazingly versatile foundation for nearly every kind of cryptographic object imaginable—along with many that were unimaginable until recently, and which still have no known constructions without LWE. Toward the practical end, LWE and its direct descendants are at the heart of several efficient real-world cryptosystems.

The Gödel Prize includes an award of USD 5,000, and is named in honor of Kurt Gödel, who was born in Austria-Hungary (now the Czech Republic) in 1906. Gödel's work has had immense impact upon scientific and philosophical thinking in the 20th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.

Gödel Prize committee:

Moses Charikar (Stanford University),

Anuj ​ ​ Dawar (Cambridge University), ​ ​

Joan Feigenbaum (Yale University),

Orna Kupferman (Hebrew University),

Giuseppe Persiano (Università di Salerno),

Omer Reingold (Stanford University).

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.