The EATCS Award 2018 - Laudatio for Noam Nisan

The EATCS Awards Committee consisting of Artur Czumaj, Christos Papadimitriou and Jean-Eric Pin (chair) has selected  Noam Nisan as the recipient of the EATCS Award 2018. The award will be presented at ICALP 2018, which will take place in Prague, Czech Republic from the 9th till the 13th of July 2018. (pdf)

The EATCS Award 2018 is awarded to Noam Nisan for his decisive influence on a range of areas in computational complexity theory and for algorithmic mechanism design, an elegant and rigorous computational theory that aptly informs economics.

In computational complexity theory, Nisan has made fundamental contributions in a broad range of areas including communication complexity, space-bounded computation, parallel computation, pseudorandom generators, computational learning theory, interactive proof systems, algebraic complexity, and the probabilistic analysis of algorithms.

He has pioneered the connection between complexity and randomness by designing pseudorandom number generators that provably fool significant machine models. He was also one of the first people to explore the deep triple connection between circuits, Fourier transforms, and learning. He wielded the algebraic self-reducibility method for interactive computation that ultimately brought us Shamir’s theorem. He has advanced, applied, and masterfully codified the all-important field of communication complexity.

His seminal paper with Ronen, along with the work of Koutsoupias and Papadimitriou on the “price of anarchy,” brought the paradigms of theoretical computer science, such as asymptotic thinking and competitive analysis, to bear on fundamental questions of economics. Since co-founding the research area of algorithmic mechanism design, Nisan has been responsible for many of its most important results.

Simply put, the techniques and thought processes initiated in the original Nisan-Ronen paper have had a revolutionary effect on the design and implementation of Google Ad Exchange in particular and of ad auctions in general. Following the success of Ad Exchange, real-time trading and online exchanges have become the de facto ways to buy and sell not only display ads but mobile, video, social, and native ads as well.

In summary, Nisan has been a dominant intellectual force in theoretical computer science for nearly three decades. He has had pervasive, deep influence in computational complexity theory and is one of the creators and leaders of algorithmic mechanism design. His work has also had immense impact outside of the theoretical computer science community, e.g., in the economics, artificial intelligence, and data networking research communities, in the Google Ad Exchange and online ad auctions more generally, and in education on both the undergraduate and graduate levels.

For all these reasons, the EATCS wants to celebrate Noam Nisan and his influential work, and is honored to award him with its most prestigious prize.

The EATCS Award Committee 2018
Artur Czumaj
Christos Papadimitriou
Jean-Eric Pin (chair) your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.