Time+Place: Thursday 12/01/2017 10:30 Room 601 Taub Bld.
Title: How to Prove the Corretness of Computations
Speaker: Ron Rothblum - CS-Lecture http://people.csail.mit.edu/ronr/
Affiliation: M I T

Abstract:


Efficient proof verification is at the heart of the study of 
computation. Seminal results such as the IP=SPACE Theorem 
[LFKN92,Shamir92] and the PCP theorem [AS92,ALMSS92] show that even 
highly complicated statements can be verified extremely efficiently.

We study the complexity of proving statements using interactive 
protocols. Specifically, what statements can be proved by a 
polynomial-time prover to a super-efficient verifier. Our main results 
show that these proof-system are remarkably powerful: it is possible to 
prove the correctness of general computations such that (1) the prover 
runs in polynomial-time, (2) the verifier runs in linear-time (and in 
some conditions in sublinear-time) and (3) the interaction consists of 
only a constant number ofcommunication rounds (and in some settings just 
a single round).

These proof-systems are motivated by, and have applications for, 
delegating computations in a cloud computing environment, and 
guaranteeing that they were performed correctly.


Short Bio:

Ron Rothblum completed his PhD at the Weizmann Institute of Science in 
2015, advised by Prof. Oded Goldreich. His dissertation received the 
John F. Kennedy Ph.D. Distinction Prize and the Shimon Even Prize in 
Theoretical Computer Science. He is currently a postdocoral associate at 
MIT. His research is focused on theoretical computer science, and 
especially cryptography and complexity theory.