@inproceedings{kalai2013delegation,
author = {Kalai, Yael Tauman and Raz, Ran and Rothblum, Ron D.},
title = {Delegation for Bounded Space},
booktitle = {In Proceedings of the 45th annual ACM symposium on Theory of computing (STOC)},
year = {2013},
month = {June},
abstract = {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). The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies, a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t(n) and space s = s(n), we construct MIPs that are sound against no-signaling strategies, where the running time of the provers is poly(t), the number of provers is O˜(s), and the running time of the verifier is O˜(s + n). We then show how to use the method suggested by Aiello et al. (ICALP, 2000) to convert our MIP into a 1-round delegation scheme, by using a computational private information retrieval (PIR) scheme. Thus, assuming the existence of a sub-exponentially secure PIR scheme, we get our 1-round delegation scheme.},
publisher = {ACM},
url = {http://approjects.co.za/?big=en-us/research/publication/delegation-bounded-space/},
edition = {In Proceedings of the 45th annual ACM symposium on Theory of computing (STOC)},
}