Gödel Prize 2014 

Computer scientists Ronald Fagin, Amnon Lotem, and Moni Naor will receive the

2014 Gödel Prize for their paper Optimal Aggregation Algorithms for Middleware, which introduced the powerful “threshold algorithm” that is widely used in applications and systems that demand optimal results for gathering multi-sourced information. The award, which recognizes outstanding papers in theoretical computer science, is presented by the European Association for Theoretical Computer Science (EATCS) and ACM’s Special Interest Group on Algorithms and Computation Theory (SIGACT). The ceremony takes place at the International Colloquium on Automata, Languages, and Programming (ICALP) July 7-11, in Copenhagen, Denmark.

The prize-winning paper provides a framework to design and analyze algorithms where aggregation of information from multiple data sources is needed, such as in information retrieval and machine learning. In these situations, the threshold algorithm offers a very efficient method for producing a single unified list of the “top k” results from the combined data sources. The threshold algorithm’s elegant mathematical properties and simplicity are particularly suitable for use in middleware, software that is often used to augment computer operating systems that support complex, distributed applications. The authors also introduced the notion of instance optimality, an extremely strong guarantee of performance, and showed that the threshold algorithm is instance optimal. The paper’s groundbreaking results have built a foundation for much follow-on research.

Ronald Fagin is an IBM Fellow at IBM Research - Almaden. He earned a B.A. degree from Dartmouth College and a Ph.D. degree from the University of California, Berkeley. A Fellow of IEEE, ACM, and the American Association for the Advancement of Science (AAAS), he was named Docteur Honoris Causa by the University of Paris, and is a member of the US National Academy of Engineering and the American Academy of Arts and Sciences. He is also a recipient of the IEEE Technical Achievement Award, the IEEE McDowell Award, and ACM SIGMOD (Special Interest Group on Management of Data) Edgar F. Codd Innovations Award.

Amnon Lotem is an algorithms and technologies expert in the Israeli high-tech industry. He served as a CTO, Chief Scientist, and algorithms group leader in several software companies. A graduate of the University of Maryland with a Ph.D. degree in Computer Science, he received a M.Sc. degree in Computer Science, and a B.Sc. degree in Mathematics and Computer Science from Tel Aviv University.

A professor of computer science at the Weizmann Institute of Science in Rehovot, Israel, Moni Naor has been with the IBM Almaden Research Center and joined the Weizmann Institute in 1993, where he is the Judith Kleeman Professorial Chair. At the Technion he earned a B.A. degree in Computer Science, and at the University of California, Berkeley he was awarded a Ph.D. degree in Computer Science. He has spent sabbatical visits at IBM Research – Almaden as well as Stanford University and Princeton University. He was named a Fellow of the International Association of Cryptologic Research.

The Gödel Prize includes an award of $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.