2023 Turing Award

Congrats to Avi Wigderson for his winning the 2023 Turing Award.

It places Avi in with some of the great theorists of all time. See for other winners: Knuth, Rabin, Scott, Cook, Karp, Hopcroft, Tarjan, Hartmanis, Blum, Yao, Rivest, Shamir, Adleman, Valiant, Micali, Goldwasser, Aho, Ullman.

Some Comments

Avi was a student of mine back at Princeton in 1983. I do recall one interesting thing. Back in those days the P=NP? problem was relatively new, having been created by Cook in 1971. We had no idea how hard its resolution was going to be. I recall Avi saying to me: “I plan on working on P=NP for a while—a few weeks.” Not too long, but as you know it is still unresolved.

Avi did prove tons of great results on things near to P=NP. Especially wonderful has been his contributions to randomness and related issues. He won the Turing Award for his work on understanding how randomness can shape and improve computer algorithms.

Open Problems

Avi says:

The [Turing] committee fooled me into believing that we were going to have some conversation about collaborating, he says. When I zoomed in, the whole committee was there and they told me. I was excited, surprised and happy.

Very clear he is a wonderful person, who is quite modest.