Efficient Verification of Computation on Untrusted Platforms

Tuesday, March 8, 2022 - 4:00pm to 5:15pm
32-G449 (Kiva)
Yael Kalai

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 quantum complexity, hardness of approximation, and the complexity of Nash equilibrium.

Milk & Cookies 4-4:15pm.