Lectures: Thursdays, 9:15 to 10:45, Room # 905 in Warren Weaver Hall
Head: Michael Chapman, Office # 408 in Warren Weaver Hall
The goal of this reading group is to study various, higher level, complexity theoretic concepts and results, all of which related to the idea of a "proof" as an interaction between a verifier and a prover, in which the prover tries to convince the verifier in the validity of some claim. This idea has its roots in cryptography, and is still a main tool therin. But, we are going to focus mainly on the complexity theoretic aspects.
The main topics that we will cover are:
The complexity classes IP and MIP, and their equivalence to PSPACE and NEXP respectively.
Probabilistically checkable proofs (PCPs)
Hardness of approximation
Zero knowledge proofs
The parallel repetition theorem
If time permits, we may dive into the quantum theory of interactive proofs. Specifically:
QIP and its equivalence to PSPACE
MIP* and its equivalence to RE
Lecture 1 , Lecture 2 , Lecture 3, Lecture 4, Notes that cover Lectures 5&6, Lecture 7 (see also Chapter 2 of Goldreich's book), Lecture 8 was based on Section 5 of BFL91,
Classical theory and cryptography:
Computational Complexity: A Modern Approach, by Arora and Barak
Lecture notes, Harsha
Lecture notes, Guruswami and O'Donnell
Lecture notes, Trevisan
Proofs, Arguments, and Zero-Knowledge, by Thaler
Quantum theory:
Quantum Proofs, by Vidick and Watrous
MIP*=RE, by Ji, Natarajan, Vidick, Wright and Yuen
The Aldous--Lyons conjecture II: Undecidability, by Bowen, Chapman and Vidick