6.S898 The Evolution of a Proof: Efficient Proof Systems in Complexity Theory, Cryptography, and Quantum Computation


Prereqs: 6.045 or 6.046
Units: 3-0-9
Schedule: TR1-2:30, room4-237
Instructor:  Professor Shafi Goldwasser, shafi@csail.mit.edu
This subject has been approved as either an AUS or as a Theoretical Computer Science concentration subject.
Efficient proof systems  in (1) complexity theory including interactive proofs, efficient arguments, cs-proofs, probabilistically checkable proofs and delegation systems with  applications to checking correctness of untrusted computation and memory storage in the cloud and approximation hardness; (2) cryptography: zero knowledge interactive and non-interactive proofs; and (3) quantum computation: interactive proofs and multi-proven interactive proofs with classical and quantum verifiers. The emphasis will be on current state of the art as well as research directions.