[Busec] 6.S898 new course on interactive & probabilistic proofs and applications

Leonid Reyzin reyzin at cs.bu.edu
Sat Aug 25 09:22:22 EDT 2012

---------- Forwarded message ----------
From: Shafi Goldwasser <shafi at theory.csail.mit.edu>
Date: Sat, Aug 25, 2012 at 1:05 AM
Subject: [Toc-visitors] 6.S898 new course on interactive & probabilistic
proofs and applications
To: toc-students at csail.mit.edu, Joanne Talbot Hanley <joanne at csail.mit.edu>,
toc-visitors at csail.mit.edu

*New Course*

* *

*6.S898  *The Evolution of a Proof

Lecturer: Shafi Goldwasser

Time/Room: TR1:00-2:30 at 4-237

* *

The last 25+ years have witnessed a remarkable development of what we mean
by “verifying the correctness of mathematical proofs and computations”.

This evolution starts with the classical notion of an NP proof which can be
verified in polynomial time in the length of the statement to be proved,
proceeds to interactive and probabilistically checkable proofs which can be
verified in randomized polynomial time, and focuses today on the search for
super efficient verification procedures for the

correctness of remotely performed computations which are also known as
delegation systems.

This progression was accompanied by the study and use of proof systems in
the context of

(1) *cryptography* with the development of zero-knowledge proof systems and

(2) verifying correctness of programs and computations as put forth in the
context of *program checking* and more recently *cloud computing* ;

(3) complexity theory to classify the tractability of *approximation
problems* and as a way to characterize traditional complexity classes; and

(4) *quantum complexity** theory* where interactive proofs with quantum
versus classical provers and verifiers is investigated.

The course will cover the development and applications of proof systems
since 1985 including interactive proofs, multi-prover interactive proofs,
zero knowledge interactive and non-interactive proofs, probabilistically
checkable proofs, proofs with computationally bounded provers (arguments,
cs-proofs, under non-falsifiable assumptions), and a special focus on
current delegation systems in the context of remote cloud computing.
Applications to cryptography, program correctness checking, remote and
distributed computing, and complexity theory will be covered as well.

Prerequisites include a theory of computation course such as 6.045 or

The lectures will be given by lecturer as well as guest lectures by Yael
Kalai and Irit Dinur.

For more information see attached syllabus or contact shafi at csail.mit.edu

Toc-visitors mailing list
Toc-visitors at lists.csail.mit.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20120825/d2adefb9/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: New Course.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 129115 bytes
Desc: not available
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20120825/d2adefb9/attachment-0001.docx>

More information about the Busec mailing list