Delegation for bounded space

We construct a 1-round delegation scheme for every language computable in time t=t(n) and space s=s(n), where the running time of the prover is poly(t) and the running time of the verifier is ~O(n + poly(s)) (where ~O hides polylog(t) factors).

Authors

• Yael Tauman Kalai
• Ran Raz
• Ron D. Rothblum

Keywords

• no-signaling proofs
• delegation