# Course Identification

Interactive and Probabilistic Proof Systems
20244132

## Lecturers and Teaching Assistants

Prof. Guy Rothblum
N/A

## Course Schedule and Location

2024
Second Semester
Monday, 14:15 - 16:00, Ziskind, Rm 155
10/04/2024
10/07/2024

## Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Elective; 2.00 points
Chemical Sciences: Elective; 2.00 points

N/A

## Prerequisites

We will assume an undergraduate-level familiarity with computational models, algebra, probability theory and algorithms. Students should also be familiar with concepts in complexity theory, such as NP-Completeness, Boolean circuits, and space complexity. A basic familiarity with cryptography will be helpful, but will not be assumed.

Students who do not have a background in complexity theory are encouraged to familiarize themselves with the material. Goldreich's book "Computational Complexity: A Conceptual Perspective" is a good source. In particular, the following chapters are most relevant:

• Preliminaries, computational models (Goldreich 1.1, 1.2)
• P, NP and NP-Completeness (Goldreich 2.1, 2.2, 2.3, 2.4)
• Boolean circuits (Goldreich 3.1)
• Space complexity (Goldreich 5.1, 5.2, 5.3, 5.4)

30

English

## Attendance and participation

Expected and Recommended

Pass / Fail

70%
30%
students will be required to prepare lecture notes

## Evaluation Type

No final exam or assignment

N/A
N/A
-
N/A

4

## Syllabus

Proof systems allow a weak verifier to ascertain the correctness of complex computational statements. . For example, to convince a verifier that a given graph contains a k-clique, a prover can supply a proof specifying the vertices in the clique, and this proof can be verified in polynomial time. Efficiently-verifiable proof systems are fundamental objects in the study of computation.

Moving beyond NP verification, studying interactive and randomized proof systems has led to some of the deepest and most celebrated insights in cryptography and in complexity theory : NP-completeness, zero-knowledge, IP=PSPACE, and the PCP Theorem. More recent advances include a developing theory of doubly-efficient interactive proofs for polynomial time computations. Here proofs can be generated in polynomial time by an honest prover, and verified in near-linear or even sub-linear time.

This course will survey these developments: from by-now-classical results on interactive proofs, to PCPs, argument systems, and doubly-efficient interactive proofs.

## Learning Outcomes

Student will become familiar with state-of-the-art results on:

• Interactive proofs
• Zero knowledge proofs
• Multi-prover interactive proofs
• Probabilistically checkable proofs
• Doubly-efficient proof systems
• Cryptographic argument systems

And their relationship to the wider study of complexity theory and cryptography.