Speaker: Guy Rothblum, Stanford University
Title: How to Verify Computations without Re-executing them
Can we prove the correctness of a polynomial-time computation to a weak verifier who cannot re-execute the computation? Such proof systems can be used in cloud computing scenarios, allowing weak devices (from phones and tablets to wearable or embedded devices) to delegate work and storage to a third party without compromising the correctness of delegated computations.
I will survey a line of work that attempts to answer this question using the machinery of interactive proofs and cryptography. The focus will be on interactive proofs with sublinear time verifiers, where with high probability the verifier accepts every input in the language, and rejects every input that is far from the language. The verifier's query complexity (and computation complexity), as well as the communication, should all be sublinear in the input length (much smaller than the complexity of deciding the language). We call such a proof system an Interactive Proof of Proximity. We show general upper and lower bounds.