Project Name

Algorithms and Theory


Prizes and Awards

2012 Godel Prize: Amir Ronen

Amir Ronen (Analytics department at IBM Research - Haifa, Israel) has been awarded the prestigious Godel Prize for 2012 by the Association for Computing Machinery (ACM). ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) together with the European Association for Theoretical Computer Science (EATCS) will recognize three groups of researchers for their contributions to understanding how selfish behavior by users and service providers impacts the behavior of the Internet and other complex computational systems.

The three selected papers are "Worst-case Equilibira" by Elias Koutsoupias and Christos H. Papadimitriou, "How Bad Is Selfish Routing?" by Tim Roughgarden and Eva Tardos, and "Algorithmic Mechanism Design" by Noam Nisan and Amir Ronen. The researchers will receive the 2012 Godel Prize at the International Colloquium on Automata, Languages and Programming (ICALP), July 9–13, in Warwick, UK.
Amir Ronen and Noam Nisan coined the term "algorithmic mechanism design" in their paper of the same title, presenting a whole new range of applications of the theory of mechanism design within computer science. Combining ideas from economics and game theory with concepts and techniques from computer science, they enriched both mechanism design and the theories of algorithms and complexity.
Before joining IBM, Amir Ronen was a post-doctoral research fellow at Stanford University and the University of California, Berkeley, he became a Senior Lecturer (Assistant Professor) in the Industrial Engineering and Management Faculty at the Technion - Israel Institute of Technology. A recipient of the Wolf Prize from the Wolf Foundation in Israel, he and Nisan were awarded the Best Paper Prize from the International Joint Conferences Artificial Intelligence (IJCAI) and the Journal of Artificial Intelligence Research (JAIR). He earned B.Sc., M.Sc., and Ph.D. degrees from the Hebrew University of Jerusalem.

2012 IEEE W. Wallace McDowell Award: Ronald Fagin

Ronald Fagin (IBM Almaden) received the IEEE W. Wallace McDowell Award for "fundamental and lasting contributions to the theory of databases". Ronald Fagin, an IBM fellow, co-authored the book "Reasoning about Knowledge," and has published more than 100 papers and served on more than 30 conference program committees and as program committee chair of four different conferences. He received his BA in mathematics from Dartmouth College, and his PhD in mathematics from the University of California at Berkeley.

2011 IEEE Technical Achievement Award: Ronald Fagin

Ronald Fagin (IBM Almaden) received the IEEE Technical Achievement Award for "for pioneering contributions to the theory of rank and score aggregation".

2003 Knuth Prize: Miklos Ajtai

Miklos Ajtai (IBM Almaden) received the Knuth Prize for "numerous ground-breaking contributions to Theoretical Computer Science", including a classic sorting network algorithm (developed jointly with J. Komlos and Endre Szemeredi), exponential lower bounds, superlinear time-space tradeoffs for branching programs, and other "unique and spectacular" results.

Best Paper Awards

  • Best Paper Award, 45th ACM Symposium on Theory of Computing (STOC 2013), Ken Clarkson and David Woodruff
  • Best Paper Award, 15th International Conference on Database Theory (ICDT 2012), Phokion Kolaitis with B. ten Cate and V. Dalmau
  • Top 10% Paper Award, 13th ACM Conference on Electronic Commerce (EC 2012), Jan Vondrak with Shahar Dobzinski
  • Alberto O. Mendelzon Test-of-Time Award, 30th ACM Symposium on Principles of Database Systems (PODS 2011), Ronald Fagin with Amnon Lotem and Moni Naor
  • Best Paper Award, 52nd IEEE Symposium on Foundations of Computer Science (FOCS 2011), Nikhil Bansal with Niv Buchbinder, Aleksander Madry and Joseph Naor
  • Best Paper Award, 26th IEEE Conference on Computational Complexity (CCC 2011), Ryan Williams
  • Best Paper Award, 29th Annual ACM Symposium on Principles of Database Systems (PODS 2010), David Woodruff with Daniel Kane and Jelani Nelson
  • Best Paper Award, 13th International Conference on Database Theory (ICDT, 2010), Ronald Fagin with Marcelo Arenas and Alan Nash
  • Best Paper Award, 18th Annual European Symposium on Algorithms (ESA 2010), Nikhil Bansal and Viswanath Nagarajan, with Anupam Gupta, Jian Li, Julian Mestre and Atri Rudra
  • Best Paper Award, 12th International Conference on Database Theory (ICDT, 2009), Phokion Kolaitis with Foto Afrati
  • An inaugural 2008 ACM PODS Alberto O. Mendelzon Test-of-Time-Award, Phokion Kolaitis
  • Best Paper Award, Fall IEEE Vehicular Technology Conference (VTC 2007), Ken Clarkson with John Hobby
  • 2005 SIAM Outstanding Paper Prize, Robert Krauthgamer with Uriel Feige (Weizmann Institute of Science; Microsoft Research)
  • Best Paper Award, 2001 ACM Symposium on Principles of Database Systems (PODS 2001), Ronald Fagin with Amnon Lotem and Moni Naor