The 2023 Turing Award is out! Why is the "randomness" of computers so important?

Last night, the Association for Computing Machinery (ACM) announced that the 2023 ACM AM Turing Award will be awarded to mathematician and top theoretical computer scientist Avi Wigderson in recognition of his foundational contributions to computational theory , including reshaping our understanding of the role of randomness in computing, and his decades of leadership in the field of theoretical computer science.

The ACM AM Turing Award was established by ACM in 1966 to honor individuals who have made significant contributions to the computer industry. The Turing Award is named after Alan M. Turing, a British scientist and pioneer in computer science. One of the purposes of establishing this award is to commemorate this great scientist.

The Turing Award has extremely high requirements for winners and a very strict award process. Generally, only one computer scientist is awarded each year, and only in a very few years do two scientists who have made contributions in the same direction win the award at the same time. Therefore, the Turing Award is also the most prestigious and noble award in the computer industry, and is known as the "Nobel Prize in the Computer Industry."

What is theoretical computer science?

Theoretical computer science is concerned with the mathematical foundations of the field. It asks questions such as, "Is this problem solvable computationally?" or "If this problem is solvable computationally, how much time and other resources would be required?" Theoretical computer science also explores the design of efficient algorithms.

Every computing technology that is closely related to our lives is realized through algorithms. Understanding the principles of powerful and efficient algorithms can not only deepen our understanding of computer science, but also deepen our understanding of the laws of nature. From cryptography and computational biology to network design, machine learning and quantum computing, breakthroughs in theoretical computer science have promoted progress in almost every field of the discipline.

Why is randomness important?

Computers are fundamentally deterministic systems; the set of algorithmic instructions applied to any given input uniquely determines its computation, and in particular, its output. In other words, deterministic algorithms follow a predictable pattern. In contrast, randomness lacks a clear pattern, or a lack of predictability in events or outcomes. Because we live in a world filled with random events such as weather systems, biological and quantum phenomena, computer scientists have enriched algorithms to make them more efficient by allowing them to make random choices during computation. In fact, many problems for which there are no known efficient deterministic algorithms have been solved efficiently using probabilistic algorithms, albeit with some small probability of error (which can be effectively reduced).

But is randomness essential, or can it be removed? And what is the quality of randomness required for probabilistic algorithms to succeed? These and many other fundamental questions are key to understanding randomness and pseudo-randomness in computing. A deeper understanding of the dynamics of randomness in computing can help us develop better algorithms and deepen our understanding of the nature of computing itself.

Wigderson's contribution

Wigderson has been a leader in computational complexity theory, algorithms and optimization, randomness and cryptography, parallel and distributed computing, combinatorics, graph theory, and the connection between theoretical computer science and mathematics and science.

For four decades, Wigderson has been a leading figure in theoretical research in computer science, making foundational contributions to the understanding of the role of randomness and pseudorandomness in computing.

Computer scientists have discovered a remarkable connection between randomness and computational difficulty (i.e., determining natural problems for which there are no efficient algorithms). Wigderson, in collaboration with colleagues, has written a series of influential books on trading randomness for difficulty. They showed that under standard, widely believed assumptions about computing, every probabilistic polynomial-time algorithm can be efficiently derandomized (i.e., completely determined).

In other words, randomness is not a necessary condition for efficient computing. This series of works completely changed our understanding of the role of randomness in computing and also changed the way we think about randomness. These seminal papers include the following three:

1) “Hardness vs. Randomness” (co-authored with Noam Nisan). Among other discoveries, this paper introduces a new type of pseudo-random generator and demonstrates that efficient deterministic simulation of randomized algorithms is possible under weaker assumptions than previously known.

Paper link: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

2) “BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs” (co-authored with László Babai, Lance Fortnow and Noam Nisan) This paper uses “hardness amplification” to prove that under weaker assumptions, bounded error probability polynomial time (BPP) can be simulated in subexponential time for infinite input lengths.

Paper link: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

3) “P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma” (co-authored with Russell Impagliazzo) This paper introduces a stronger pseudo-random generator that achieves a nearly optimal trade-off between hardness and randomness.

Paper link: https://dl.acm.org/doi/pdf/10.1145/258533.258590

Importantly, the impact of these three papers went far beyond the field of randomness and derandomization. The ideas in these papers were later applied to many areas of theoretical computer science and led to influential papers by several leaders in the field. Later, Wigderson, in collaboration with Omer Reingold, Salil Vadhan, and Michael Capalbo, continued to work in the broad field of computational randomness, and in another paper proposed the first efficient combinatorial construction of extended graphs, which are sparse graphs with strong connectivity. They have many important applications in both mathematics and theoretical computer science.

Paper link: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf

In addition to his research on randomness, Wigderson is a leader in several areas of theoretical computer science, including multi-verifier interactive proofs, cryptography, and circuit complexity.

Respected mentor

In addition to his groundbreaking technical contributions, Wigderson was recognized as a respected mentor and colleague, advising countless young researchers. His breadth of knowledge and excellent technical ability, combined with his kindness, enthusiasm, and generosity, enabled him to attract many of the best young people to the field of theoretical computer science.

"It is important to note that Avi Wigderson has also received the Abel Prize, considered the most important honor for lifetime achievement in mathematics," said ACM President Yannis Ioannidis. "Avi Wigderson's work on randomness and other topics has set the direction for theoretical computer science over the past three decades," explained Jeff Dean, Google's senior vice president of research. "From the dawn of computer science, researchers have recognized that randomness is a way to design faster algorithms for a wide range of applications. Efforts to better understand randomness continue to bring important benefits to our field, and Wigderson has broken new ground in this area."

Wigderson's resume

Wigderson has been the Herbert H. Maas Professor of Mathematics at the Institute for Advanced Study in Princeton since 1999. Previously, he was a professor at the Hebrew University of Jerusalem and a visiting professor at Princeton University, the University of California, Berkeley, and IBM.

Wigderson graduated from the Technion-Israel Institute of Technology and received his MS, MSE, and PhD in Computer Science from Princeton University. His honors include the Abel Prize, the IMU Abacus Prize, the Donald E. Knuth Prize, the Edsger W. Dijkstra Award for Distributed Computing, and the Gödel Prize. He is a Fellow of the ACM, the U.S. National Academy of Sciences, and the American Academy of Arts and Sciences.

Reference link: https://awards.acm.org/about/2023-turing