![\"New](\"https:\/\/images.newscientist.com\/wp-content\/uploads\/2024\/04\/08121417\/SEI_198618497.jpg?width=1200\")
<\/div>Avi Wigderson, winner of the 2023 Turing award<\/p>\n
Peter Badge<\/p>\n<\/div>\n<\/figcaption><\/figure>\n<\/p>\n
The mathematician Avi Wigderson<\/a> has won the 2023 Turing award, often referred to as the Nobel prize for computing, for his work on understanding how randomness can shape and improve computer algorithms.<\/p>\n Wigderson, who also won the prestigious Abel prize<\/a> in 2021 for his mathematical contributions to computer science, was taken aback by the award. \u201cThe [Turing] committee fooled me into believing that we were going to have some conversation about collaborating,\u201d he says. \u201cWhen I zoomed in, the whole committee was there and they told me. I was excited, surprised and happy.\u201d<\/p>\n Computers work in a predictable way<\/a> at the hardware level, but this can make it difficult for them to model real-world problems, which often have elements of randomness and unpredictability. Wigderson, at the Institute for Advanced Study in Princeton, New Jersey, has shown over a decades-long career that computers can also harness randomness in the algorithms that they run.<\/p>\n In the 1980s, Wigderson and his colleagues discovered that by inserting randomness into some algorithms, they could make them easier and faster to solve, but it was unclear how general this technique was. \u201cWe were wondering whether this randomness is essential, or maybe you can always get rid of it somehow if you\u2019re clever enough,\u201d he says.<\/p>\n <\/p>\n One of Wigderson\u2019s most important discoveries was making clear the relationship between types of problems, in terms of their difficulty to solve, and randomness. He also showed that certain algorithms that contained randomness and were hard to run could be made deterministic, or non-random, and easier to run.<\/p>\n These findings helped computer scientists better understand one of the most famous unproven conjectures in computer science, called \u201cP \u2260 NP<\/a>\u201d, which proposes that easy and hard problems for a computer to solve are fundamentally different. Using randomness, Wigderson discovered special cases where the two classes of problem were the same.<\/p>\n Wigderson first started exploring the relationship between randomness and computers in the 1980s, before the internet existed, and was attracted to the ideas he worked on by intellectual curiosity, rather than how they might be used. \u201cI\u2019m a very impractical person,\u201d he says. \u201cI\u2019m not really motivated by applications.\u201d<\/p>\n However, his ideas have become important for a wide swath of modern computing applications, from cryptography to cloud computing. \u201cAvi\u2019s impact on the theory of computation in the last 40 years is second to none,\u201d says Oded Goldreich<\/a> at the Weizmann Institute of Science in Israel. \u201cThe diversity of the areas to which he has contributed is stunning.\u201d<\/p>\n One of the unexpected ways in which Wigderson\u2019s ideas are now widely used was his work, with Goldreich and others, on zero-knowledge proofs, which detail ways of verifying information without revealing the information itself. These methods are fundamental for cryptocurrencies<\/a> and blockchains<\/a> today as a way to establish trust between different users.<\/p>\n Although great strides in the theory of computation have been made over Wigderson\u2019s career, he says that the field is still full of interesting and unsolved problems. \u201cYou can\u2019t imagine how happy I am that I am where I am, in the field that I\u2019m in,\u201d he says. \u201cIt\u2019s bursting with intellectual questions.\u201d<\/p>\n Wigderson will receive a $1 million prize as part of the Turing award.<\/p>\n