Mathematician Who Shed Light On Randomness In Algorithms Wins Top Prize In Computing
Source: Smithsonian Magazine, Christian Thorsberg
Photo: Avi Wigderson is the first recipient of both a Turing Award and an Abel Prize, math’s top honor. (Andrea Kane/Institute for Advanced Study)
The 2023 Turing Award—the computing world’s Nobel Prize equivalent—has been given to mathematician Avi Wigderson for his groundbreaking and widely applicable contributions to computer science. The honor comes with a $1 million prize.
Over his decades-long career, the 67-year-old Institute for Advanced Study professor concerned himself with whether a problem could be solved, rather than what the answer might be—part of a specialization known as theoretical computer science.
“As far as we know, for every problem that we face and try to solve, we can’t rule out that it has an algorithm that can solve it,” Wigderson tells Quanta Magazine’s Stephen Ornes. “This is the single most interesting problem for me.”
At the center of his work are randomness and unpredictability. Computers tend to work in a predictable way, following determined patterns. But beginning with his research in the early 1980s, Wigderson discovered that in some instances, adding unknowns—or randomness—to particular algorithms could turn up a solution more easily and quickly. And conversely, he found that randomness could be removed from other algorithms, making it easier to arrive at a solution.
His work to study and refine this relationship—between randomness and a problem’s difficulty and solvability—has had profound impacts on modern computing.
“It’s very hard to work in any space in computer science without actually intersecting with Avi’s work,” Madhu Sudan, a computer scientist at Harvard University who collaborated with Wigderson on research in the past, says to Quanta Magazine. “And everywhere, you find very deep insights.”
Yannis Ioannidis, president of the Association for Computing Machinery, the organization that awards the Turing prize, called Wigderson a “towering intellectual force in theoretical computer science,” in a statement this week.
His contributions, for example, helped researchers make better sense of one of the field’s most famous unproven conjectures, called the P versus NP problem. It asks: If the solution to a problem is easy to verify, is the problem itself easy to solve? The conjecture suggests easy and hard problems for computers are fundamentally different. With randomness, Wigderson helped clarify particular proofs and discover unique instances in which both easy and hard problems were the same.
Wigderson also wrote about how concepts in theoretical computing can be applied to various natural and human-made processes—randomness could play a role in solving hard problems, such as finding a cure for cancer, writes the New York Times’ Cade Metz. Randomness governs lots of processes in the world, from stock markets, to internet gossip, to the spread of disease and the activity of bacteria in a Petri dish.
As such, the impact of Wigderson’s work has expanded far beyond computer science. The modern fields of cryptography, cloud computing and blockchain development are all imbued with principles and discoveries from Wigderson.
For instance, his work with randomness and algorithms helped advance zero-knowledge protocols, a crucial method within computer security that allows for the transfer and confirmation of sensitive information between parties. In its most simple working, one party is able to prove that a condition is true to another party, without revealing any other details. Random, unique digital keys also help secure online data.
In another testament to how describing and harnessing randomness stretches across multiple fields, the discipline has recently received recognition in math. The 2024 Abel Prize, the world’s top award in mathematics, was given to French mathematician Michel Talagrand last month for his advances in stochastic systems, which help model random variables more precisely.
Among a variety of other awards, Wigderson won the 2021 Abel Prize—along with mathematician László Lovász—for work that helped connect math with computer science. This new honor makes Wigderson the only person to win both a Turing Award and an Abel Prize.
“Avi’s impact on the theory of computation in the last 40 years is second to none,” Oded Goldreich, a computer science professor at the Weizmann Institute of Science in Israel, tells New Scientist’s Alex Wilkins. “The diversity of the areas to which he has contributed is stunning.”
For all his achievements in predictability, one process that Wigderson didn’t solve was his own Turing Award announcement.
“The [Turing] committee fooled me into believing that we were going to have some conversation about collaborating,” Wigderson tells New Scientist. “When I zoomed in, the whole committee was there and they told me. I was excited, surprised and happy.”
Christian Thorsberg is an environmental writer and photographer from Chicago. His work, which often centers on freshwater issues, climate change and subsistence, has appeared in Circle of Blue, Sierra magazine, Discover magazine and Alaska Sporting Journal.