The ACM announced that Avi Wigderson, a force in computational complexity and beyond, will receive the 2023 A. M. Turing Award (Quanta article). This is the first primarily complexity theorist to win the award since Andy Yao in 2000. Avi can add this to his Abel, Nevanlinna and Knuth prizes. Avi has served on the faculty at the Institute for Advanced Study since 1999 after many years at Hebrew University. He’s hosted many postdocs and visiting faculty and students who’ve gone onto great careers of their own.
Avi is my first co-author to win the Turing award. Our paper was just one link in a chain of papers, from Nisan-Wigderson to Impagliazzo-Wigderson showing how circuit bounds yield derandomization. Philosophically these results tell us randomness is just computation we cannot predict.
But Avi did so much more. NP has zero-knowledge proofs. Zig-Zag expanders that led to Reingold’s SL = L. Monotone circuit lower-bounds using communication complexity. Upper and lower bound for matching. Optimal Extractors. And that’s just the tip of the iceberg.
Notably none of these papers are solely authored or even have much overlap in their author lists. Avi shared his wisdom with many, nearly 200 distinct co-authors according to DBLP.
Beyond his research, Avi has been a great advocate for our field, advocating to the NSF as a founding member of the SIGACT Committee for the Advancement for Theoretical Computer Science, and on the Simons Foundation scientific board which led to Simons Fellows and the Simons Institute. Avi wrote a book placing computational complexity as a great mathematical discipline that just also happens to have great applications in so many different fields.
Congrats to Avi and this capstone to an incredible career and individual.