By Stephen DeAngelis
Albert Einstein believed curiosity is one of humanity’s best traits. He once wrote, “The important thing is to not stop questioning. Curiosity has its own reason for existence. One cannot help but be in awe when he contemplates the mysteries of eternity, of life, of the marvelous structure of reality. It is enough if one tries merely to comprehend a little of this mystery each day.”[1] One man who has remained curious his whole live is the mathematician Avi Wigderson, who was just awarded the Turing Award for his wide-ranging contributions to the theory of computation.
For four years now, I have given copies of Professor Wigderson’s book Mathematics + Computation: A Theory Revolutionizing Technology and Science to colleagues of mine at Massive Dynamics™ and Enterra® as a fundamental treatise of computational complexity theory as applied to mathematics and across natural and social scientific domains. It describes the underlying principles of computational complexity theory in a clear and understandable manner and provides a theoretical framework for some of our work. It is a wonderful contribution to the field.
Science writer Stephen Ornes explains, "For more than 40 years, Avi Wigderson has studied problems. But as a computational complexity theorist, he doesn’t necessarily care about the answers to these problems. He often just wants to know if they’re solvable or not, and how to tell."[2] Wigderson is an optimist. He explains, “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. This is the single most interesting problem for me.”[3]
He is no stranger to winning awards. "Wigderson received the Nevanlinna Prize in 1994 for his work on computational complexity. Along with Omer Reingold and Salil Vadhan, he won the 2009 Gödel Prize for work on the zig-zag product of graphs, a method of combining smaller graphs to produce larger ones used in the construction of expander graphs. Wigderson was elected as a member of the American Academy of Arts and Sciences in 2011. He was elected to the National Academy of Sciences in 2013. He was elected as an ACM Fellow in 2018 for 'contributions to theoretical computer science and mathematics.' In 2019, Wigderson was awarded the Knuth Prize for his contributions to 'the foundations of computer science in areas including randomized computation, cryptography, circuit complexity, proof complexity, parallel computation, and our understanding of fundamental graph properties.' In 2021 Wigderson shared the Abel Prize with László Lovász 'for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.'"[4]
Concerning Wigderson's latest award, science journalist Alex Wilkins writes, "[The] Turing award [is] often referred to as the Nobel prize for computing."[5] Wigderson learned about his latest award over the internet. He explains, "The [Turing] committee fooled me into believing that we were going to have some conversation about collaborating. When I zoomed in, the whole committee was there and they told me. I was excited, surprised and happy.”[6] Similar to Nobel prizes, the Turing Award comes with a $1 million bonus.
Like Einstein before him, Wigderson works at the Institute for Advanced Study, Princeton, where he serves as Herbert H. Maass Professor at the School of Mathematics. He indicates that his main research interests include: Randomness and Computation; Algorithms and Optimization; Complexity Theory; Circuit Complexity; Proof Complexity; Quantum Computation and Communication; and, Cryptography and Distributed Computation.
Congratulations Professor Wigderson for this latest well-deserved honor.
Footnotes
[1] Albert Einstein, “Old Man’s Advice to Youth: ‘Never Lose a Holy Curiosity.’,” Life, 2 May 1955.
[2] Stephen Ornes, "Avi Wigderson, Complexity Theory Pioneer, Wins Turing Award," Quanta Magazine, 10 April 2024.
[3] Ibid.
[4] "Avi Wigderson," Wikipedia.
[5] Alex Wilkins, "Mathematician wins Turing award for harnessing randomness," New Scientist, 10 April 2024. [6] Ibid.
