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, 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, 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.

Madhu Sudan, a computer scientist at Harvard University who won the 2002 Rolf Nevanlinna Prize (now called the Abacus Prize), said Wigderson’s influence on the field is impossible to miss. “It’s very hard to work in any space in computer science without actually intersecting with Avi’s work,” Sudan said. “And everywhere, you find very deep insights.” In the late 1980s, for example, Sudan worked with Wigderson on a paper investigating connections between certain mathematical functions and polynomials. That work launched Sudan’s entire career. “This is typical for Avi,” said Sudan. “He gets into some space, he asks the right questions, and then he moves on.”

Wigderson grew up in Haifa, Israel, as one of three sons of a nurse and an electrical engineer, both survivors of the Holocaust. His father loved puzzles and was intensely interested in fundamental ideas in math, which he shared with his children. “He’s the guy from whom I was infected by this virus,” Wigderson said. When he started college in the 1970s, at the Technion in Haifa, he wanted to major in math, but his parents steered him instead to computer science. “They thought maybe it was a good idea that I would have a job when I’m done,” he said.

Keep reading at quantamagazine.org.

To learn more about Professor Avi Wigderson, watch the video below.

Top photo credit: Rami Shulsh, Office of the Technion Spokesperson