Abstract:

I will discuss some well-known and less-known papers of Turing, exemplify the scope of deep, prescient ideas he put forth, and mention follow-up work on these by the Theoretical CS community.

No special background will be assumed.

Biography:

Avi Wigderson is the Herbert H. Maass Professor in School of Mathematics at the Institute for Advanced Study. He received his B.Sc. in Computer Science from Technion in 1980, and his Ph.D. in Computer Science from Princeton University in 1983. After post-doctorate positions in UC Berkeley, IBM research, and MSRI, Avi joined the faculty of the Computer Science department at the Hebrew University starting 1986. In 1999, Avi joined IAS as faculty in the School of Math and founded the Computer Science and Discrete Mathematics program. His research interests are in computational complexity theory, algorithms and optimization, randomness and cryptography, parallel and distributed computation, combinatorics, and graph theory, as well as connections between theoretical computer science and mathematics and science. Avi has received many awards, including the 2021 Abel Prize (along with László Lovász) and most recently the 2023 ACM A.M. Turing Award for foundational contributions to the theory of computation, and for his decades of intellectual leadership in theoretical computer science.