The Taub Faculty of Computer Science Events and Talks
Ron Rothblum - CS-Lecture
Thursday, 12.01.2017, 10:30
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.
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.