Probabilistic Proof Systems

3 Credits · Level: Graduate, Undergraduate

Classically, a mathematical proof of a theorem is something that can be written down and efficiently checked line by line. However, over the last 30 years, computer scientists have introduced a variety of nonclassical notions of proofs. These can be broadly described as "probabilistic proof systems", because they fundamentally involve randomness. The study of probabilistic proof systems has led to many exciting developments in cryptography and theoretical computer science over the last three decades. This course will describe a variety of probabilistic proof systems and their applications to cryptography and complexity theory. Topics include interactive proofs, multi-prover interactive proofs, probabilistically checkable proofs, zero-knowledge proofs, and proofs secure against computationally bounded provers (i.e., argument systems). Particular attention will be devoted to recent applications of probabilistic proof systems to cloud computing and cryptocurrencies. There are no formal prerequisites for this course. However, mathematical maturity will be expected.