PCP and Delegating Computation: A Love Story.

Computer Science/Discrete Mathematics Seminar I
Topic:PCP and Delegating Computation: A Love Story.
Speaker:Yael Tauman Kalai
Affiliation:Microsoft Research
Date:Monday, January 28
Time/Room:11:00am - 12:00pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2019/0128-YaelTaumanKalai

In this talk, I will give an overview on how PCPs, combined with cryptographic tools, are used to generate succinct and efficiently verifiable proofs for the correctness of computations. I will focus on constructing (computationally sound) *succinct* proofs that are *non-interactive* (assuming the existence of public parameters) and are *publicly verifiable*. In particular, I will focus on a recent result with Omer Paneth and Lisa Yang, where we show how to construct such proofs for all polynomial time computations, based on an efficiently falsifiable decisional assumption on groups with bilinear maps. Prior to this work, this was only known under non-standard assumptions.