Efficient Probabilistic Proofs

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.

Organizers:

Nir Bitansky, Tel Aviv University
Alessandro Chiesa, UC Berkeley
Ron Rothblum, Technion

Logistics:

Roberta Partisani, Centro Universitario Residenziale di Bertinoro

Sponsors:

• Home
• Program
• Registration
• Participants
• Location

• The workshop will happen in July 2022. Please contact the organizers if you are interested to participate.

• The workshop has been postponed again, from summer 2021 to summer 2022 due to the ongoing pandemic. We are optimistic for an in-person gathering then!

• The workshop has been postponed from summer 2020 to summer 2021 due to the pandemic.