What is known worldwide as the “Nobel Prize of Computing,” the A.M. Turing Award for 2024 will be granted to Prof. Avi Wigderson, a graduate of the Henry and Marilyn Taub Faculty of Computer Science at the Technion-Israel Institute of Technology in Haifa.
The award is an annual prize given by the ACM (the American Association for Computing Machinery). The recipient, whose award was announced on Thursday, is a researcher at the Institute for Advanced Study (IAS) at Princeton University in New Jersey. In June 2023, he received an honorary doctorate from the Technion for “his significant contribution and leadership in the fields of computer science theory and discrete mathematics, including complexity theory, cryptography, expanding graphs, and more; and in gratitude for his long-standing relationship with the Technion, beginning with his undergraduate studies.”
The ACM said it granted him the prestigious award for “foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation, and for his decades of intellectual leadership in theoretical computer science.”
Wigderson, born in Haifa in 1956, completed his undergraduate degree in the Technion’s Faculty of Computer Science at the Technion in 1980. He went on to earn a master’s degree and doctorate at Princeton, where he currently serves as a researcher at the Institute for Advanced Study.
Over the years, he has published hundreds of articles and has won numerous awards and scholarships, including the Alon Fellowship, the Gödel Prize, the Knuth Prize, the Abel Prize and the Nevanlinna Prize. Wigderson is also an author. His book, Mathematics and Computation: A Theory Revolutionizing Technology and Science, makes the field of complexity accessible and explains its connections to computer science theory.
Theoretical computer science is concerned with the mathematical underpinnings of the field. It poses questions such as “Is this problem solvable through computation?” or “If this problem is solvable through computation, how much time and other resources will be required?” It also explores the design of efficient algorithms. Every computing technology that touches our lives is made possible by algorithms.
Understanding principles for creating efficient algorithms
Understanding the principles that make for powerful and efficient algorithms deepens our understanding not only of computer science, but also the laws of nature. While theoretical computer science is known as a field that presents exciting intellectual challenges and is often not directly concerned with improving the practical applications of computing, research breakthroughs in this discipline have led to advances in almost every area of the field—from cryptography and computational biology to network design, machine learning, and quantum computing.
Fundamentally, computers are deterministic systems; the set of instructions of an algorithm applied to any given input uniquely determines its computation and, in particular, its output. In other words, the deterministic algorithm is following a predictable pattern. Randomness, by contrast, lacks a well-defined pattern, or predictability in events or outcomes. Because the world we live in seems full of random events (weather systems, biological and quantum phenomena, and more), computer scientists have enriched algorithms by allowing them to make random choices in the course of their computation, in the hope of improving their efficiency.
Indeed, many problems for which no efficient deterministic algorithm was known have been solved efficiently by probabilistic algorithms, albeit with some small probability of error (that can be efficiently reduced).
These, and many other fundamental questions lie at the heart of understanding randomness and pseudo-randomness in computation. An improved understanding of the dynamics of randomness in computation can lead us to develop better algorithms as well as deepen our understanding of the nature of computation itself.
A leader in theoretical computer science research for four decades, Wigderson has made foundational contributions to the understanding of the role of randomness and pseudo-randomness in computation.
Computer scientists have discovered a remarkable connection between randomness and computational difficulty (identifying natural problems that have no efficient algorithms). Working with colleagues, Wigderson authored a highly influential series of works on trading hardness for randomness.
They proved that, under standard and widely believed computational assumptions, every probabilistic polynomial time algorithm can be efficiently de-randomized (namely, made fully deterministic). In other words, randomness is not necessary for efficient computation. This sequence of works revolutionized our understanding of the role of randomness in computation, and the way we think about randomness.
Outside of his work in randomness, Wigderson has been an intellectual leader in several other areas of theoretical computer science, including multi-prover interactive proofs, cryptography, and circuit complexity. In addition to his groundbreaking technical contributions, Wigderson is recognized as an esteemed mentor and colleague who has advised countless young researchers. His vast knowledge and unrivaled technical proficiency—coupled with his friendliness, enthusiasm, and generosity—have attracted many of the best young minds to pursue careers in theoretical computer science.
Technion president Prof. Uri Sivan, congratulated Wigderson and said: “We are very proud of the fact that he is a Technion alumnus with a long-standing connection to our community of researchers. Last year, we conferred on him an honorary doctorate for his groundbreaking contribution to a wide spectrum of subjects, from discrete mathematics to complex cryptography. His winning of the Turing Award proves that the world recognizes his seminal contributions. We congratulate him on this huge honor and rejoice together with him.”
Prof. Danny Raz, the dean of the Taub Faculty of Computer Science added: “Prof. Wigderson’s immense contributions to the realms of mathematics and computing have earned him international recognition. He serves as a role model for our graduates, embodying the Technion spirit as an alumnus who, since completing his studies, has dedicated his career to advancing human knowledge. A brilliant researcher in both mathematics and computer science, and at their interface, he is truly deserving of this esteemed award.”
“It’s important to point out that Avi Wigderson also received the Abel Prize, which is considered the most important honor for lifetime achievements in the field of mathematics,” explained ACM President Yannis Ioannidis. “Being selected for the ACM A.M.
Turing Award is a fitting follow-up—as mathematics is foundational to computer science and Wigderson’s work has connected a wide range of mathematical sub-areas to theoretical computer science. He is a towering intellectual force in theoretical computer science, an exciting discipline that attracts some of the most promising young researchers to work on the most difficult challenges.
This year’s Turing Award recognizes his specific work on randomness, as well as the indirect but substantial impact he has had on the entire field of theoretical computer science.”
