Proofs'22

July 17-22, 2022

University Residential Center

Bertinoro (Forlì-Cesena), Italy

The discovery and study of probabilistic proof systems, such as PCPs and IPs, have had a tremendous impact on theoretical computer science. These proof systems have numerous applications (e.g., to hardness of approximation) but one of their most compelling uses is a direct one: to construct cryptographic protocols that enable super fast verification of long computations. In this setting, the efficiency of the cryptographic protocol is often dominated by that of the underlying probabilistic proof system.

The last few years have seen a surge of interest in the design and analysis of efficient probabilistic proofs, leading to new paradigms and even real-world deployments. This workshop will focus on the frontiers of this new area, with a particular emphasis on identifying and discussing the main open problems in the design of efficient (information-theoretic) probabilistic proofs.