The mathematician who shed light on randomness in algorithms wins the first prize in computer science

The 2023 Turing Award, the computing world’s equivalent of the Nobel Prize, has been awarded to mathematician Avi Wigderson for his innovative and broadly applicable contributions to computing. The honor comes with a $1 million prize.

During his decades-long career, the 67-year-old Institute for Advanced Study professor was concerned with whether a problem could be solved, rather than what the answer might be in a specialization known as theoretical computing .

As far as we know, for every problem we face and try to solve, we can’t rule out that it has an algorithm that can solve it, Wigderson says. Quanta magazines Stephen Ornes. This is the most interesting problem for me.

At the center of his work is chance and unpredictability. Computers tend to work in predictable ways, following certain patterns. But starting with his research in the early 1980s, Wigderson discovered that in some cases, adding an unknown or randomness to particular algorithms could lead to an easier and faster solution. Conversely, he found that randomness could be removed from other algorithms, making it easier to reach a solution.

His work to study and refine this relationship between randomness and the difficulty and solvability of problems has had profound impacts on modern computing.

It’s very difficult to work in any space of computing without actually crossing paths with Avis’ work, says Madhu Sudan, a computer scientist at Harvard University who has collaborated with Wigderson on research in the past. Quanta magazine. And everywhere, you will find very deep knowledge.

Yannis Ioannidis, president of the Association for Computing Machinery, the organization that awards the Turing Award, called Wigderson a towering intellectual force in theoretical computing, in a statement this week.

His contributions, for example, helped researchers better understand one of the field’s most famous untested conjectures, called the P versus NP problem. Question: If the solution to a problem is easy to verify, is the problem easy to solve? The conjecture suggests that easy and hard problems for computers are fundamentally different. By chance, Wigderson helped clarify particular proofs and discover unique cases where easy and hard problems were the same.

Wigderson also wrote about how the concepts of theoretical computing can be applied to various natural and man-made processes, chance could play a role in solving difficult problems, such as finding a cure for cancer, he writes the News from New York Cade Metz Chance governs many processes in the world, from stock markets to Internet gossip to the spread of disease to the activity of bacteria in a petri dish.

As such, the impact of Wigderson’s work has expanded far beyond computing. The modern fields of cryptography, cloud computing, and blockchain development are steeped in Wigderson’s principles and discoveries.

Avi Wigderson, Turing Award 2023 Q&A with David Nirenberg | Institute of Advanced Studies

For example, his work with randomness and algorithms helped advance zero-knowledge protocols, a crucial method within computer security that allows the transfer and confirmation of sensitive information between parties. In its simplest operation, one party is able to demonstrate that a condition is true to another party, without revealing any other details. Unique and random digital keys also help protect data online.

In another testament to how the description and exploitation of randomness extends into various fields, the discipline has recently received recognition in mathematics. The 2024 Abel Prize, the world’s most important prize in mathematics, was awarded last month to French mathematician Michel Talagrand for his advances in stochastic systems, which help model random variables more accurately.

Among a variety of other awards, Wigderson won the 2021 Abel Prize along with mathematician Lszl Lovsz for work that helped connect mathematics with computing. This new honor makes Wigderson the only person to have won both a Turing Award and an Abel Award.

Avis’ impact on the theory of computation over the past 40 years is unparalleled, according to Oded Goldreich, a professor of computer science at the Weizmann Institute of Science in Israel. New Scientists Alex Wilkins. The diversity of areas in which he has contributed is impressive.

For all his successes in predictability, one process that Wigderson did not solve was his own announcement of the Turing Award.

The [Turing] The committee misled me into believing we were going to have a conversation about collaborating, says Wigderson New Scientist. When I zoomed in, the whole committee was there and they told me. I was excited, surprised and happy.