Course Identification

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)

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.

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.