Kudos: Let’s hear it for theoretical computer scientists. Without their work, we would not be carrying around a mini computer in our pockets. Perhaps even more importantly, we couldn’t accurately predict the weather or be on the edge of reliable quantum computing. Avi Wigderson rightly deserves recognition in this field for work that has widely influenced so many others.
On Wednesday, the Association for Computing Machinery, a prestigious organization in the field of computer science, awarded mathematician Avi Wigderson the Turing Award. This award, often called the Nobel Prize of Computing, is named after Alan Turing, a pioneer in the field. It is considered one of the highest honors in computer science and comes with a million-dollar cash prize, reflecting the significant impact of the recipient’s work.
Wigderson is a theoretical computer scientist specializing in randomness, cryptography, computational complexity, and other related pursuits. He works as an advanced mathematics professor at the Institute for Advanced Study at Princeton, New Jersey.
Theoretical computer scientists tackle questions like, “Is this problem solvable through computation?” or “If this problem is solvable through computation, how much time and other resources will be required?”
It also delves into the realm of computer algorithm optimization. Just because a line of code is the most obvious way to execute a task does not mean it is the most efficient way. So Wigderson and others in the field are indirectly responsible for breakthroughs in everything from cryptography to machine learning.
Avi Wigderson *83 has won the #ACMTuringAward from @TheOfficialACM!
The award is considered the highest honor in computer science, often called the “Nobel Prize of Computing.”
Congratulations! �’� https://t.co/g9KOK1llTy
– Princeton University (@Princeton) April 10, 2024
Wigderson has led theoretical research that has laid the foundations for computational randomness and pseudorandomness in systems for forty years. It was long thought that chaotic systems like the weather or quantum mechanics are impossible to model using deterministic instructions because of those systems’ inherent random behavior.
In a series of studies, Wigderson and his colleagues challenged widely believed computational assumptions by proving that all probabilistic polynomial time algorithms can be “derandomized” efficiently and be made fully deterministic. Derandomization is the process of converting a probabilistic algorithm into a deterministic one, which has significant implications for the efficiency and reliability of computational processes.
“In other words, randomness is not necessary for efficient computation,” the ACM notes. “This sequence of works revolutionized our understanding of the role of randomness in computation, and the way we think about randomness.”
Wigderson’s seminal works include the papers “Hardness vs Randomness,” “BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs,” and “P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma.” These papers, co-authored by contemporaries like Noam Nisan and Lance Fortnow, became foundational material for other studies in theoretical computer science.
As a professor, Wigderson has mentored students and colleagues alike. He has a passion for his field of study and an enthusiasm for sharing his knowledge with everyone he meets.
“Notably, none of these papers are solely authored or even have much overlap in their author lists,” Fortnow wrote in his blog regarding his colleague’s achievement. “Avi shared his wisdom with many, nearly 200 distinct co-authors according to DBLP. Congrats to Avi and this capstone to an incredible career and individual.”
Image credit: Association for Computing Machinery
