Gödel Prize 2014 to Ronald Fagin, Amnon Lotem, and Moni Naor for Optimal Aggregation Algorithms for Middleware

Ronald Fagin, Amnon Lotem, and Moni Naor will receive the 2014 Gödel Prize for their paper Optimal Aggregation Algorithms for Middleware (http://researcher.watson.ibm.com/researcher/files/us-fagin/jcss03.pdf), 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) http://icalp2014.itu.dk/ 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. 

Congratulations to the award recipients and many thanks to the Gödel Prize Committee for this year!