Avi Wigderson, Complexity Theory Pioneer, Wins Turing Award
The prolific researcher found deep connections between randomness and computation and spent a career influencing cryptographers, complexity researchers and more.
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. “The situation is ridiculous,” said Wigderson(opens a new tab), a computer scientist at the Institute for Advanced Study in Princeton, New Jersey. No matter how hard a question seems, an efficient way to answer it could be hiding just out of reach. “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.”
Today Wigderson was named the winner of the A.M. Turing Award(opens a new tab), widely considered one of the top honors in computer science, for his foundational contributions to the theory of computation. Wigderson’s work has touched nearly every area of the field. His colleagues, collaborators, and mentees say he consistently finds unexpected bridges between disparate areas. And his work on randomness and computation, starting in the 1990s, revealed deep connections between mathematics and computer science that underlie today’s investigations.