Avi Wigderson

New York, NY, April 10, 2024 – ACM, the Association for Computing Machinery, today named Avi Wigderson as recipient of the 2023 ACM A.M. Turing 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 is the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey. He has been a leading figure in areas including computational complexity theory, algorithms and optimization, randomness and cryptography, parallel and distributed computation, combinatorics, and graph theory, as well as connections between theoretical computer science and mathematics and science.

The ACM A.M. Turing Award, often referred to as the “Nobel Prize of Computing,” carries a $1 million prize with financial support provided by Google, Inc. The award is named for Alan M. Turing, the British mathematician who articulated the mathematical foundations of computing.

What is Theoretical Computer Science?

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?”

Theoretical computer science also explores the design of efficient algorithms. Every computing technology that touches our lives is made possible by 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.

Why is Randomness Important?

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, etc.), 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. And 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). But is randomness essential, or can it be removed? And what is the quality of randomness needed for the success of probabilistic algorithms?

These, and many other fundamental questions lie at the heart of understanding randomness and pseudorandomness 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.

Wigderson’s Contributions

A leader in theoretical computer science research for four decades, Wigderson has made foundational contributions to the understanding of the role of randomness and pseudorandomness in computation.

Computer scientists have discovered a remarkable connection between randomness and computational difficulty (i.e., 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 derandomized (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. This series of influential papers include the following three:

• “Hardness vs. Randomness” (co-authored with Noam Nisan)
  Among other findings, this paper introduced a new type of pseudorandom generator, and proved that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than previously known.
• “BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs” (co-authored with László Babai, Lance Fortnow, and Noam Nisan)
  This paper used `hardness amplification’ to demonstrate that bounded-error probabilistic polynomial time (BPP) can be simulated in subexponential time for infinitely many input lengths under weaker assumptions.
• “P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma” (co-authored with Russell Impagliazzo)
  This paper introduces a stronger pseudo-random generator with essentially optimal hardness vs randomness trade-offs.

Importantly, the impact of these three papers by Wigderson goes far beyond the areas of randomness and derandomization. Ideas from these papers were subsequently used in many areas of theoretical computer science and led to impactful papers by several leading figures in the field.

Still working within the broad area of randomness in computation, in papers with Omer Reingold, Salil Vadhan, and Michael Capalbo, Wigderson gave the first efficient combinatorial constructions of expander graphs, which are sparse graphs that have strong connectivity properties. They have many important applications in both mathematics and theoretical computer science.

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.

Mentoring

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.

ACM has named 56 members ACM Fellows for significant contributions in areas including computer architecture, mobile networks, robotics, and systems security. The accomplishments of the 2018 ACM Fellows underpin the technologies that define the digital age and greatly impact our professional and personal lives. ACM Fellows are composed of an elite group that represents less than 1% of the Association’s global membership.

"In society, when we identify our tech leaders, we often think of men and women in industry who have made technologies pervasive while building major corporations,” said ACM President Cherri M. Pancake. “At the same time, the dedication, collaborative spirit and creativity of the computing professionals who initially conceived and developed these technologies goes unsung. The ACM Fellows program publicly recognizes the people who made key contributions to the technologies we enjoy. Even when their work did not directly result in a specific technology, they have made major theoretical contributions that have advanced the science of computing. We are honored to add a new class of Fellows to ACM’s ranks and we look forward to the guidance and counsel they will provide to our organization."

Underscoring ACM’s global reach, the 2018 Fellows hail from universities, companies and research centers in Finland, Greece, Israel, Sweden, Switzerland, and the US.

The 2018 Fellows have been cited for numerous contributions in areas including accessibility, augmented reality, algorithmic game theory, data mining, storage, software and the World Wide Web.

ACM will formally recognize its 2018 Fellows at the annual Awards Banquet, to be held in San Francisco on June 15, 2019. Additional information about the 2018 ACM Fellows, and the awards event, as well as previous ACM Fellows, is available through the ACM Fellows site.