Abstract:

Efficient verification of computation is fundamental to computer science and is at the heart of the P vs. NP question. Recently it has had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud computing. In this talk, I will present schemes for verifying the correctness of a computation. I will discuss both their practical aspects and their impact on cryptography, quantum complexity, hardness of approximation, and the complexity of finding a Nash equilibrium.

Bio:

Yael Tauman Kalai is a Senior Principal Researcher at Microsoft Research and a Professor at the Massachusetts Institute of Technology (MIT). Kalai earned a BSc in Mathematics from the Hebrew University of Jerusalem, an MS in Computer Science and Applied Mathematics from The Weizmann Institute of Science, and a PhD in Computer Science from the Massachusetts Institute of Technology. Kalai's honors include an Outstanding Master's Thesis Prize (Weizmann Institute of Science, 2001), the George M. Sprowls Award for Best Doctoral Thesis in Computer Science (MIT, 2007). She is the recipient of the 2022 ACM Prize in Computing and is a Fellow of the International Association for Cryptologic Research (IACR). Additionally, Kalai was an invited speaker at the International Congress of Mathematics (ICM, 2018).