Fall 2019

Interactive Proofs (Part I)

Monday, Aug. 26, 2019 9:30 am10:30 am PDT

Add to Calendar


Justin Thaler (Georgetown University)

This tutorial will introduce the notion of interactive proofs, which are protocols that enable a computationally weak verifier to offload computations to a powerful but untrusted prover. The tutorial will survey the main techniques underlying the design of efficient interactive proofs, including arithmetization and low-degree extensions, the sum-check protocol, and the notion of doubly-efficient interactive proofs. No prior knowledge will be assumed.