Probabilistic Proof Systems in Theory and Practice

Probabilistic proof systems allow a powerful prover to convince a computationally weak verifier of the validity of a large and complex computation. These seemingly magical objects have been an extremely important tool both in theory, where they have driven breakthroughs like the PCP theorem, zero-knowledge proofs, and advancements in approximation hardness, and in practice, where they are integral to the scalability of cloud computing and blockchain technology and are widely deployed, securing billions of dollars worth of transactions.

In this short introduction talk, I will give an overview of research topics related to cryptographic proof systems that interest me.