ACM Awards Knuth Prize to Pioneer of Algorithmic Game Theory
Hebrew University's Nisan Cited for Fundamental and Lasting Contributions to Theoretical Computer Science
New York, September 8, 2016 —The 2016 Donald E. Knuth Prize will be awarded to Noam Nisan of the Hebrew University of Jerusalem for fundamental and lasting contributions to theoretical computer science in areas including communication complexity, pseudorandom number generators, interactive proofs, and algorithmic game theory. The Knuth Prize is jointly bestowed by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the IEEE Computer Society Technical Committee on the Mathematical Foundations of Computing (TCMF). It will be presented at the 57th Annual Symposium on Foundations of Computer Science (FOCS 2016) in New Brunswick, NJ, October 9–11.
Nisan’s work has had a fundamental impact on complexity theory, which examines which problems could conceivably be solved by a computer under limits on its resources, whether it is on its computation time, space used, amount of randomness or parallelism. One of the major ways in which computer scientists have explored the complexity limits is through the use of randomized algorithms. Nisan has made major contributions exploring the power of randomness in computations. His work designing pseudorandom number generators has offered many insights on whether, and in what settings, the use of randomization in efficient algorithms can be reduced.
Nisan has been a major player in Algorithmic Game Theory, and, through his 1999 paper with Amir Ronen, has laid the foundation of Algorithmic Mechanism Design. A mechanism is an algorithm or protocol that is explicitly designed so that rational participants, motivated purely by their self-interest, will achieve the designer's goals. This is of paramount importance in the age of the Internet, with many applications from auctions to network routing protocols. Nisan has designed some of the most effective mechanisms by providing the right incentives to the players. He has also shown that in a variety of environments there is a tradeoff between economic efficiency and algorithmic efficiency. Nisan is a co-editor of Algorithmic Game Theory, a fundamental text in the field.
He is also a leading authority in communication complexity, an area of computer science research that examines the amount of information that needs to be transferred between parties for computational problems. With Eyal Kushilevitz, Nisan co-authored Communication Complexity, an authoritative text in the field.
Nisan is professor of computer science and engineering at the Hebrew University of Jerusalem. He is also a graduate of Hebrew University, and earned his Ph.D. from the University of California, Berkeley. He received the 2012 Gödel Prize (with Elias Koutsoupias, Christos Papadimitriou, Amir Ronen, Tim Roughgarden and Éva Tardos), the 1990 ACM Doctoral Dissertation Award for his dissertation, “Using Hard Problems to Create Pseudorandom Generators,” and the 2004 Michael Bruno Memorial Award.
The Donald E. Knuth Prize is named in honor of Donald Knuth of Stanford University who has been called the “father of the analysis of algorithms.” The annual award recognizes outstanding contributions to the foundations of computer science by individuals for their overall impact in the field over an extended period, and includes a $5,000 award.
About ACM SIGACT
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.
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.
Contact:
Jim Ormond
ACM
212-626-0505
[email protected]
Michael Mitzenmacher
ACM SIGACT Chair
617-496-7172
[email protected]