Proofs are at the foundations of mathematics, and verifying the correctness of a mathematical proof is a
fundamental computational task. (The P versus NP problem, which deals precisely with the complexity of proof
verification, is one of the most important open problems in all of mathematics.) The complexity-theoretic study of
proof verification has led to new notions of mathematical proofs, such as Interactive Proofs, Probabilistically
Checkable Proofs, and others.

Probabilistic proofs are a powerful tool for proving hardness of approximation results, and are an essential
building block to achieve delegation of computation (protocols that enable super fast verification of long
computations, such as SNARKs). Via these applications, probabilistic proofs have had a tremendous impact on
theoretical computer science and, more recently, are playing an exciting role in applied cryptography, computer
security, and blockchain technology (e.g., they help secure billions of dollars in transactionds per day).

This course provides an introduction to probabilistic proofs and the beautiful mathematics underlying them.
Covered topics include arithmetization, the sumcheck protocol, zero knowledge, doubly-efficient interactive
proofs, linearity testing, low-degree testing, proof composition, succinct verification, and more.

This courses assumes basic familiarity with algorithms (asymptotic notation and analysis of algorithms),
complexity theory (computation models and simple complexity classes), and some algebra (finite fields and their
properties).