ACM Group Presents Gödel Prize for Designing Innovative Algorithms

Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources

New York, May 1, 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 ACM’s Special Interest Group on Algorithms and Computation Theory (SIGACT) and the European Association for Theoretical Computer Science (EATCS). The ceremony takes place at the International Colloquium on Automata, Languages, and Programming (ICALP) July 7-11, in Copenhagen, Denmark.

Their 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 the 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 IBM Research – Almaden and joined the Weizmann Institute in 1993, where he is the Judith Kleeman Professorial Chair. At the Technion-Israel Institute of Technology 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.

About ACM

ACM, the Association for Computing Machinery, is the world's largest educational and scientific computing society, uniting educators, researchers, and professionals to inspire dialogue, share resources, and address the field's challenges. ACM strengthens the computing profession's collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.


The ACM Special Interest Group on Algorithms and Computation Theory fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science. The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.


The European Association for Theoretical Computer Science is an international organization aimed at promoting research in the wide field of the foundations of computer science (ranging from formal languages, abstract computation models, algorithm design and complexity analysis, to applications of logic and semantics in programming). It facilitates the exchange of ideas and results among computer scientists, in particular through the organization of the annual International Conference on Automata, Languages and Programming (ICALP).


Paul Beame




Virginia Gold



printable pdf file