Probabilistic Proofs

Catalog description

This course offers a graduate-level introduction to the theory of probabilistic proof systems. The area has deep connections to many aspects of theoretical computer science, including complexity theory and hardness of approximation, coding theory, cryptography and quantum computing. Topics covered will include the PCP theorem, interactive proofs, zero knowledge, succinct arguments, and quantum proof systems.