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.