This work concerns two-message interactive proof systems (with computational soundness) in which the verification time is almost linear and the (honest) prover strategy can be implemented in polynomial time. Such proof systems are obtained for any set in SC (see a more general and accurate stmt in the abstract).
The proof uses an odd model of MIP systems, and shows that (1) a known transformation of MIP systems to the desired interactive proof systems that may fail in general is sound when applied to systems of this odd model, and (2) that adeqaute schemes can be constructed in the odd model. Hence, odd or not, this odd model (aka no-signaling) proved useful.
The authors believe that they can extend the result to any set in P; the last details are currently being verified and a proof will be posted soon (hopefully).
Update (Dec'13): The prophecy made in the prior paragraph was just fulfilled; see ECCC TR13-183.
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 $\pl(t)\cdot(n + poly(s))$, where $\pl(t)=\polylog t$.
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 $\pl(t)\cdot s$, and the running time of the verifier is $\pl(t)\cdot(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.