Randomness in computation wins computer-science ‘Nobel’
Published in Nature
Computer scientist Avi Wigderson is known for clarifying the role of randomness in algorithms, and for studying their complexity.
By Davide Castelvecchi
Avi Wigderson pictured outdoors at the Institute for Advanced Study.
Avi Wigderson received the Turing Award for his foundational contributions to the theory of computation.Credit: Dan Komoda
A leader in the field of computational theory is the latest winner of the A. M. Turing Award, sometimes described as the ‘Nobel Prize’ of computer science.
Avi Wigderson at the Institute for Advanced Study (IAS) in Princeton, New Jersey, is known for work straddling several disciplines, and had already won a share of the Abel Prize, a top mathematics award, three years ago.
He receives the Turing Award “for foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation, and for his decades of intellectual leadership in theoretical computer science”, the Association for Computing Machinery (ACM) in New York City announced on 10 April.
“I was extremely happy, and I didn’t expect this at all,” Wigderson tells Nature. “I’m getting so much love and appreciation from my community that I don’t need prizes.”
‘A towering intellectual force’
Wigderson was born in Haifa, Israel, in 1956. He studied at Technion — Israel Institute of Technology in Haifa and later at Princeton University; he has been at the IAS since 1999. He is known for his work on computational complexity — which studies how certain problems are inherently slow to solve, even in principle — and on randomness in computation. Many practical algorithms make random choices to achieve their objectives more efficiently; in a series of groundbreaking studies in the 1990s, Wigderson and his collaborators showed that conventional, deterministic algorithms can, in principle, be roughly as efficient as ‘randomized’ ones1. The results helped to confirm that random algorithms can be as accurate as deterministic ones are.
“Wigderson is a towering intellectual force in theoretical computer science,” said ACM president Yannis Ioannidis in a statement. In addition to Wigderson’s academic achievements, the ACS cited his “friendliness, enthusiasm, and generosity”, which have led him to be a mentor to or collaborate with hundreds of researchers worldwide. Wigderson admits that he is a “big proselytizer” of the intellectual pleasures of his discipline — he wrote a popular book about it and made it freely available on his website. “I think this field is great, and I am happy to explain it to anybody.”
The Turing Award is named after the celebrated British mathematician and code-breaker Alan Turing (1912–54), who in the 1930s laid the conceptual foundations of modern computing. “I feel completely at home with mathematics,” says Wigderson, adding that as an intellectual endeavour, theoretical computer science is indistinguishable from maths. “We prove theorems, like mathematicians.”
Websites
- Quanta
- ACM
References
Impagliazzo, R. & Wigderson, A. in Proc. 29th ACM Symposium on Theory of Computing 220–229 (ACM, 1997).
No comments:
Post a Comment