<br><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Shafi Goldwasser</b> <span dir="ltr">&lt;<a href="mailto:shafi@theory.csail.mit.edu">shafi@theory.csail.mit.edu</a>&gt;</span><br>

Date: Sat, Aug 25, 2012 at 1:05 AM<br>Subject: [Toc-visitors] 6.S898 new course on interactive &amp; probabilistic proofs and applications<br>To: <a href="mailto:toc-students@csail.mit.edu">toc-students@csail.mit.edu</a>, Joanne Talbot Hanley &lt;<a href="mailto:joanne@csail.mit.edu">joanne@csail.mit.edu</a>&gt;, <a href="mailto:toc-visitors@csail.mit.edu">toc-visitors@csail.mit.edu</a><br>

<br><br><div dir="ltr">














<p class="MsoNormal" style="text-align:center" align="center"><b><u><span style="font-size:12.5pt;font-family:Arial;color:#222222;background:white">New Course</span></u></b></p>

<p class="MsoNormal" style="text-align:center" align="center"><u><span style="color:rgb(34,34,34);font-size:12.5pt;font-family:Arial;background-image:initial"><span style="text-decoration:none"> </span></span></u></p>


<p class="MsoNormal" style="text-align:center" align="center"><font><u><span style="color:rgb(34,34,34);font-family:Arial">6.S898  </span></u><span style="font-family:Arial;color:rgb(34,34,34);background:none repeat scroll 0% 0% white">The Evolution of a Proof<span>  </span></span></font></p>







<p class="MsoNormal" style="text-align:center" align="center"><font><span style="font-family:Arial;color:rgb(34,34,34);background:none repeat scroll 0% 0% white"> </span></font></p><p class="MsoNormal" style="text-align:center" align="center">


<font><span style="font-family:Arial;color:rgb(34,34,34);background:none repeat scroll 0% 0% white">Lecturer:
Shafi Goldwasser <span> </span></span></font></p>

<p class="MsoNormal" style="text-align:center" align="center"><font><span style="font-family:Arial;color:rgb(34,34,34);background:none repeat scroll 0% 0% white">Time/Room:
TR1:00-2:30 at 4-237</span></font></p>

<p class="MsoNormal" style="margin-left:.5in;text-indent:.5in"><font face="Arial"><br></font></p>

<p class="MsoNormal" style="text-align:center" align="center"><u><span style="font-size:12.5pt;font-family:Arial;color:#222222;background:white"><span style="text-decoration:none"> </span></span></u></p>

<p class="MsoNormal"><span style="font-family:Arial;color:rgb(34,34,34)"><br>
<span style="background-image:initial">The last 25+ years have witnessed a remarkable
development of what we mean by “verifying the correctness of mathematical
proofs and computations”.</span></span></p>

<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">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 </span></p><p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">correctness of remotely performed computations which are
also known as delegation systems. </span></p>

<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial"> </span></p>

<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">This progression was accompanied by the study and use of
proof systems in the context of </span></p><p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">(1) <b>cryptography</b>
with the development of zero-knowledge proof systems and arguments;<span>  </span></span></p><p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">(2) verifying correctness of programs
and computations as put forth in the context of <b>program checking</b> and more recently <b>cloud computing</b><span> ; </span></span></p><p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">(3) complexity
theory to classify the tractability of <b>approximation
problems</b> and as a way to characterize traditional complexity classes; and </span></p><p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">(4) <b>quantum complexity</b><i> theory</i> where interactive proofs with
quantum versus classical provers and verifiers is investigated. </span></p>

<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial"> </span></p>

<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">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.</span></p>

<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial"> </span></p>

<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">Prerequisites include a theory of computation course such as
6.045 or 6.046. </span></p><p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">The lectures will be given by lecturer as well as guest
lectures by Yael Kalai and Irit Dinur. </span></p><p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial">For more information see attached syllabus or contact
<a href="mailto:shafi@csail.mit.edu" target="_blank">shafi@csail.mit.edu</a></span></p>

<p class="MsoNormal"><span style="color:rgb(34,34,34);font-family:Arial;background-repeat:initial initial;background-image:initial"> </span></p>

</div>
<br>_______________________________________________<br>
Toc-visitors mailing list<br>
<a href="mailto:Toc-visitors@lists.csail.mit.edu">Toc-visitors@lists.csail.mit.edu</a><br>
<a href="https://lists.csail.mit.edu/mailman/listinfo/toc-visitors" target="_blank">https://lists.csail.mit.edu/mailman/listinfo/toc-visitors</a><br>
<br></div><br>