The Taub Faculty of Computer Science Events and Talks

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.