Clark School Home UMD

ISR News Story

Alum Amnon Lotem wins EATCS/ACM SIGACT Gödel Prize

Alumnus Amnon Lotem (CS Ph.D. 2000) and co-authors Ronald Fagin (IBM Research—Almaden) and Moni Naor (Weizmann Institute of Science) have been honored with the 2014 Gödel Prize for their paper, “Optimal Aggregation Algorithms for Middleware.” Lotem was advised at Maryland by Professor Dana Nau (CS/ISR).

The paper introduced the powerful “threshold algorithm” that is widely used in applications and systems that demand optimal results for gathering multi-sourced information. It 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.

Lotem first started pursuing the ideas in the paper in a course on databases during his time at Maryland. His instructor suggested he examine an idea for improving the existing “Fagin’s algorithm” in data aggregation. Lotem created an optimal algorithm for the defined problem, and he and the instructor, Mike Franklin, subsequently co-authored on a paper that summarized both algorithms, and analyzed optimal aggregation algorithms for middleware.

Lotem is an algorithms and technologies expert in the Israeli high-tech industry. The prize will be awarded in July at the 41st International Colloquium on Automata, Languages, and Programming in Copenhagen.

The Gödel Prize recognizes outstanding papers in theoretical computer science and is presented by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery’s Special Interest Group on Algorithms and Computation Theory (ACM SIGACT).

Related Articles:
Oct. 4 event features Michele Gelfand, research colleague of Dana Nau
Five recipients of ISR Graduate Student Travel Award announced
Dana Nau to be inducted into Duke alumni society
Alumna Mingyan Liu named ECE chair at University of Michigan
Best paper award for Bergbreiter, St. Pierre, Gosrich at Hilton Head workshop
Alum Mingyan Liu is PI for Multiscale Network Games of Collusion and Competition MURI
Nau, Gelfand, Goldstein part of MURI developing the potential of mean-field game theory
Alumnus Philip Twu's exciting career in space robotics
Kedem, De Oliveira win Canadian Journal of Statistics Award
ISR researchers win additional $948K NSF Neural and Cognitive Systems grant

May 4, 2014


Prev   Next

 

 

Current Headlines

Pines Receives UMD President's Medal

Sennur Ulukus receives NSF grant to address important data-related medical device issue

NSF grant for Ghodssi, Bentley furthers research of flexible devices to combat biofilms

Oct. 4 event features Michele Gelfand, research colleague of Dana Nau

Fermuller, Shamma, Etienne-Cummings receive NSF grant for 'Research Coordination Network'

Alumnus Omur Ozel joins George Washington University as tenure-track faculty

Lu, Gollob, Picard win ISR annual awards

Five recipients of ISR Graduate Student Travel Award announced

These are tiny robots. And they are awesome.

MTI App that Rewards Smart Commuting Featured in Washington Post

News Resources

Return to Newsroom

Search News

Archived News

Events Resources

Events Calendar