Ron Rothblum: How to Delegate Computations: The Power of No-Signaling Proofs

465 views · Published 7 May 2014 · 42:46 · Indexed 14 November 2026

Channel: Hebrew University of Jerusalem · 2014 · Education

Watch on YouTube

Ron Rothblum (Weizmann Inst.)
How to Delegate Computations: The Power of No-Signaling Proofs

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval scheme.

More from this channel