Logo

Mathematical Sciences Research Institute

Home » Foundations and Frontiers of Probabilistic Proofs (Virtual School)

Summer Graduate School

Foundations and Frontiers of Probabilistic Proofs (Virtual School) July 26, 2021 - August 06, 2021
Parent Program: --
Location: Virtual
Organizers Alessandro Chiesa (University of California, Berkeley), Tom Gur (University of Warwick)
Lecturer(s)

Show List of Lecturers

Teaching Assistants(s)

Show List of Teaching Assistant's

Speaker(s)

Show List of Speakers

Description
Proofs main logo
Several executions of a 3-dimensional sumcheck protocol with a random order of directions (thanks to Dev Ojha for creating the diagram)

Proofs are at the foundations of mathematics. Viewed through the lens of theoretical computer science, verifying the correctness of a mathematical proof is a fundamental computational task. Indeed, 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 exciting reenvisionings of mathematical proofs. For example, probabilistically checkable proofs (PCPs) admit local-to-global structure that allows verifying a proof by reading only a minuscule portion of it. As another example, interactive proofs allow for verification via a conversation between a prover and a verifier, instead of the traditional static sequence of logical statements. The study of such proof systems has drawn upon deep mathematical tools to derive numerous applications to the theory of computation and beyond.

In recent years, such probabilistic proofs received much attention due to a new motivation, delegation of computation, which is the emphasis of this summer school. This paradigm admits ultra-fast protocols that allow one party to check the correctness of the computation performed by another, untrusted, party. These protocols have even been realized within recently-deployed technology, for example, as part of cryptographic constructions known as succinct non-interactive arguments of knowledge (SNARKs).

This summer school will provide an introduction to the field of probabilistic proofs and the beautiful mathematics behind it, as well as prepare students for conducting cutting-edge research in this area.

Courses. The summer graduate school will start with two days of introductory material for everyone, covering definitions and simple examples of interactive proofs and probabilistically checkable proofs. Subsequently, two complementary courses will be offered:

  • foundations course, covering the "classics" of probabilistic proofs. The material includes seminal results that have found a diverse set of applications in theoretical computer science.
  • frontiers course, covering contemporary results in probabilistic proofs. The focus of this course is on proof protocols for delegating computations.

Students are encouraged to attend both courses, which have comparable difficulty and are designed to complement each other.

Suggested prerequisites

(1) Fundamentals of computational complexity.
For example, chapters 1,2,4,6,7 of Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. Most importantly:

  • Turing machines, complexity classes, and reductions (1.2-1.5, 2.2).
  • The Cook-Levin theorem (2.3).
  • Familiarity with the classes P, NP, PSPACE, NEXP, and their complete languages (1.6, 2.1, 2.6, 4.1, 4.2).
  • The computation model of Boolean circuits, circuit satisfiability, and exponential size circuits (6.1-6.4, 6.8).
  • Probabilistic computation and the class BPP (7.1-7.4).

(2) Basic knowledge of finite fields and their properties.
For example, as covered in the following references:

Bibliography

For eligibility and how to apply, see the Summer Graduate Schools homepage

Due to the small number of students supported by MSRI, only one student per institution will be funded by MSRI.

Keywords and Mathematics Subject Classification (MSC)
Tags/Keywords
  • algebraic local-to-global phenomena; probabilistic proof systems; SNARGs

Primary Mathematics Subject Classification
Secondary Mathematics Subject Classification No Secondary AMS MSC
Schedule, Notes/Handouts & Videos
Show Schedule, Notes/Handouts & Videos
Show All Collapse
Jul 26, 2021
Monday
09:15 AM - 09:30 AM
  Welcome: Introduction to the summer school
Alessandro Chiesa (University of California, Berkeley)
09:30 AM - 10:30 AM
  Lecture A.1: Intro to IPs
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.1: Intro to PCPs
Tom Gur (University of Warwick)
12:30 PM - 01:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.0: Warm-Up
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.0: Warm-Up
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Jul 27, 2021
Tuesday
09:30 AM - 10:30 AM
  Lecture A.2: Sumcheck Protocol
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.2: Linearity Testing
Tom Gur (University of Warwick)
12:30 PM - 01:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.1: Intro to IPs
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.1: Intro to PCPs
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Jul 28, 2021
Wednesday
09:30 AM - 10:30 AM
  Lecture A.3: IP for PSPACE
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.3: Low-Degree Testing
Tom Gur (University of Warwick)
01:00 PM - 02:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.2: Sumcheck Protocol
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.2: Linearity Testing
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Jul 29, 2021
Thursday
09:30 AM - 10:30 AM
  Lecture A.4: Doubly-Efficient IPs
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.4: FRI Protocol
Tom Gur (University of Warwick)
01:00 PM - 02:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.3: IPs for PSPACE
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.3: Low-Degree Testing
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Jul 30, 2021
Friday
09:30 AM - 10:30 AM
  Lecture A.5: Zero-Knowledge IPs
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.5: Analysis of FRI
Tom Gur (University of Warwick)
01:00 PM - 02:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.4: Doubly-Efficient IPs
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.4: Intro to FRI Protocol
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Aug 02, 2021
Monday
09:30 AM - 10:30 AM
  Lecture A.6: Limitations of IPs
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.6: Exp-size PCP
Tom Gur (University of Warwick)
01:00 PM - 02:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.5: Zero-Knowledge IPs
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.5: Analysis of FRI Protocol
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Aug 03, 2021
Tuesday
09:30 AM - 10:30 AM
  Lecture A.7: Intro to IOPs
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.7: Poly-size PCP
Tom Gur (University of Warwick)
01:00 PM - 02:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.6: Limitations of IPs
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.6: Exponential-Size PCPs
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Aug 04, 2021
Wednesday
09:30 AM - 10:30 AM
  Lecture A.8: Linear-size IOP for Circuits
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.8: PCPs with Sublinear Verification
Tom Gur (University of Warwick)
01:00 PM - 02:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.7: Intro to IOPs
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.7: Polynomial-Size PCPs
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Aug 05, 2021
Thursday
09:30 AM - 10:30 AM
  Lecture A.9: Linear-Size IOP for Machines
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.9: Proof Composition
Tom Gur (University of Warwick)
01:00 PM - 02:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.8: Linear-Size IOPs for Circuits
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.8: PCPs with Sublinear Verification
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)
Aug 06, 2021
Friday
09:30 AM - 10:30 AM
  Lecture A.10: Limitations of PCPs and IOPs
Alessandro Chiesa (University of California, Berkeley)
11:00 AM - 11:30 AM
  Break
11:30 AM - 12:30 PM
  Lecture B.10: Applications of PCPs
Tom Gur (University of Warwick)
01:00 PM - 02:00 PM
  Break
02:00 PM - 03:00 PM
  Recitation A.9: Linear-Size IOPs for Machines
Gal Arnon (The Weizmann Institute), Nick Spooner (Boston University)
03:00 PM - 04:00 PM
  Recitation B.9: Proof Composition
Marcel Dall'Agnol (University of Warwick), Inbal Livni Navon (The Weizmann Institute)