He made major contributions to parallel algorithms, cryptography and complexity theory
Mathematician Avi Wigderson of the Institute for Advanced Study (IAS) in Princeton has been awarded the 2023 Turing Award. This prestigious award, created by the Association for Computing Machinery (ACM) to recognize contributions to the field of computer science, includes a financial incentive of $1,000,000, thanks to the support of Google. It is named after the mathematician Alan Turing, whose research underlies modern computing theory.
The prize was awarded to Wigderzon for his fundamental contributions to the theory of computing and his leading role in the development of theoretical computer science. In particular, his work on the role of randomness in computing led to a change in the general understanding of this issue. Wigderzon is also the 2021 Abel Prize recipient, making him the first person to receive both prestigious awards.
He is recognized for his research in derandomization and pseudorandomness, which has brought a deep understanding of the importance of randomness in computing. Together with Noam Nisan, he published an influential paper in 1994 demonstrating that randomness is not necessary for efficient problem solving. This study ruled out the possibility of the advantage of probabilistic algorithms and outlined the role of determinism in computer science.
Avi Vigderzon was born in Israel and received his PhD in computer science from Princeton in 1983. He has made significant contributions to various areas of computer science, including parallel algorithms, cryptography, and complexity theory.
In his research, Wigderzon also draws attention to the fact that calculations occur not only in computers, but throughout the world around us. He emphasizes that the laws of nature that operate in all natural processes can also be expressed using mathematical formulas and algorithms. Thus, his research has broad applications in various scientific fields, including statistical and quantum physics, computational biology, economics and social sciences.
In a commentary about his scientific work, Vigderzon notes that his research is theoretical in nature: «I am not motivated by applications. But I know that this fundamental work has applications. Think about Alan Turing. He published a mathematical paper on logic in an obscure journal. She was not motivated by application. But this is where computer science begins. He himself admitted that the Model he proposed was so simple that it was easy to create».
In the mid-1980s, Wigderzon, along with Silvio Micali and Oded Goldreich, extended the idea of interactive zero-knowledge proofs to NP-complete problems. They showed that the solution to every such problem can be proven using a zero-knowledge proof.
«We have discovered that anything that can be proven can be proven without revealing new information», — Wigderzon explained. «The motivation for this research came from cryptography, where I wanted to prove that I had chosen the secret key correctly without revealing it. The result is a very general approach that is now used in blockchains and other cryptosystems. Sometimes I am surprised by the hard work of people who are interested in practical implementation and want to see how everything works».
Avi Vigderzon remains an active scientist. He is delighted by the opportunity to collaborate with new groups of young scientists every year. One of his current projects is generalizing convex optimization theory to non-Euclidean conditions. This area has wide applications in machine learning, signal processing, computer vision and automatic control systems. Wigderzon's project aims to generalize the theory to manifolds, which are found in various areas of mathematics and physics, such as quantum information theory and invariant theory, as well as in computer science. This theory is also used in analysis to prove inequalities and in algebra to prove identities. It is widely applicable, and this inspires me», — he noted.