EE Seminar: How to prove the correctness of computations

(The talk will be given in English)

Speaker: Dr. Ron Rothblum

Weizmann Institute

Monday, January 2nd, 2017 15:00 - 16:00

Room 011, Kitot Bldg., Faculty of Engineering

How to prove the correctness of computations

Abstract

Efficient proof verification is at the heart of the study of computation. Seminal results such as the IP=PSPACE 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 of communication 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.