Israeli mathematician Avi Wigderson wins $1 million Turing Award 2023
Avi Wigderson, an esteemed mathematician from Israel, has been awarded the prestigious Turing Award for 2023. The annual accolade is presented by the Association for Computing Machinery (ACM) to individuals who have made significant and enduring contributions to computing. Often referred to as the "Nobel Prize of computing," the Turing Award is named after British computer scientist and mathematician Alan Turing, a key figure in the birth of computer science. The Turing Award was first presented in 1966.
Wigderson's research revolutionizes computer algorithms
Wigderson's award-winning research focuses on utilizing randomness to improve computer algorithms. His innovative work has made a substantial impact in the field of computer science. "The [Turing] committee fooled me into believing that we were going to have some conversation about collaborating," said Wigderson. "When I zoomed in, the whole committee was there and they told me. I was excited, surprised and happy," he added.
Exploration of randomness in computational problem-solving
Wigderson has dedicated decades to research at the Institute for Advanced Study in Princeton, exploring the relation between randomness and computational problem-solving. In a significant shift from conventional thinking in the 1980s, Wigderson and his team discovered that incorporating randomness into algorithms could improve their efficiency. He explained, "We were wondering whether this randomness is essential, or maybe you can always get rid of it somehow if you're clever enough."
Impact on the 'P ≠ NP' debate in computer science
One of Wigderson's notable achievements is his work on elucidating the relationship between problem complexities and the role of randomness. His research has significantly influenced an ongoing debate in computer science known as "P ≠ NP." The question P ≠ NP asks whether every problem whose solution can be quickly verified can also be solved quickly. By employing randomness, Wigderson identified particular situations where the distinction between simple and complex computational problems becomes indistinct.
