Knuth award to Noam Nisan

Mazel tov to Noam Nisan!

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-authoredCommunication 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.”