Tutorials with exercises
-
Overview of "practical" probabilistic proofs
This surveys the landscape of "practical" probabilistic proofs.
slides (610 kB), video -
Linear PCPs and the role of Quadratic Arithmetic Programs (QAPs)
This tutorial reviews linear PCPs, which are at the heart of many "practical" probabilistic proofs.
slides and exercises (732 kB), video -
Folklore arithmetization of programs
This tutorial explains how various program constructs (conditionals, equality tests, inequalities, etc.) are represented as systems of equations over a finite field.
slides and exercises (2 MB), video
(Owing to a production error, the slide video is out of sync with the rest of the presentation.)
In these slides, grey boxes are explicit exercises.
The slides also contain "blanks" that the presentation fills in, by writing on the slides. You can either try to fill these in as further exercises, or watch the videos.
These presentations are all excerpts from the 2016 Bar-Ilan Winter School on Verifiable Computation.
Comprehensive survey of proofs, arguments, and zero knowledge
This comprehensive survey by Justin Thaler covers probabilistic proofs, with emphasis on "practical" protocols.