| Year |
Laureate |
Reasons |
| 1982 |
Robert Tarjan |
"Received the first Nevanlinna Prize for outstanding contributions to mathematical aspects of information science. "Pure mathematics enjoys the luxury of studying its constructions, whether finite or infinite, in complete independence of all questions of efficiency." explained Jacob Schwartz, who spoke on Tarjan's work. "By contrast, theoretical computer science must ultimately concern itself with computing engines which operate with limited speed and data storage, and therefore must take efficiency as one of its central concerns. Two closely related activities, algorithm design and algorithm analysis, grow out of this inevitable concern."[8] |
| 1986 |
Leslie Valiant |
"Valiant has contributed in a decisive way to the growth of almost every branch of the fast growing young tree of theoretical computer science, his theory of counting problems being perhaps his most important and mature work."[9] |
| 1990 |
Alexander Razborov |
"For his groundbreaking work on lower bounds for circuit complexity."[10] |
| 1994 |
Avi Wigderson |
"For his outstanding work on the mathematical foundations of computer science. The objects of research there include, for example, finding efficient methods for solving complex tasks as well as upper and lower bounds for the computational effort for certain problems. Wigderson made a significant contribution to understanding the paradoxical term "zero-knowledge interactive proofs".[11] |
| 1998 |
Peter Shor |
"For his outstanding work on quantum computation and in particular for deriving the Shor's algorithm." |
| 2002 |
Madhu Sudan |
"For important contributions to several areas of theoretical computer science, including probabilistically checkable proofs, non-approximability of optimization problems, and error-correcting codes." |
| 2006 |
Jon Kleinberg |
"For deep, creative and insightful contributions to the mathematical theory of the global information environment, including the influential "hubs and authorities"-algorithm; methods for discovering short chains in large social networks; techniques for modeling, identifying and analyzing bursts in data streams; theoretical models of community growth in social networks; and contributions to the mathematical theory of clustering." |
| 2010 |
Daniel Spielman[12] |
"For smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing." |
| 2014 |
Subhash Khot[13] |
"For his prescient definition of the “Unique Games” problem, and leading the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems; his work has led to breakthroughs in algorithmic design and approximation hardness, and to new exciting interactions between computational complexity, analysis and geometry."[14] |
| 2018 |
Constantinos Daskalakis[15] |
"For transforming our understanding of the computational complexity of fundamental problems in markets, auctions, equilibria, and other economic structures. His work provides both efficient algorithms and limits on what can be performed efficiently in these domains."[16] |
| 2022 |
Mark Braverman |
"For his path-breaking research developing the theory of information complexity, a framework for using information theory to reason about communication protocols. His work has led to direct-sum theorems giving lower bounds on amortized communication, ingenious protocol compression methods, and new interactive communication protocols resilient to noise."[17] |
