Verifier Non-Locality in Interactive Proofs
This introduces a new tool and liability for protocol design and analysis in computational complexity, but it appears incremental as it builds on known MIP frameworks without specifying broad applications.
The paper tackles the problem of the verifier's role in multi-prover interactive proofs, revealing that the verifier can intrinsically provide non-local resources for provers, which challenges existing soundness proofs that assume otherwise.
In multi-prover interactive proofs, the verifier interrogates the provers and attempts to steal their knowledge. Other than that, the verifier's role has not been studied. We have discovered that the verifier plays a much more important role than previously thought. Simply put, the verifier has the capability of providing non-local resources for the provers intrinsically. Existing MIPs' proofs of soundness implicitly depend on the fact that the verifier is not a non-local resource provider. The verifier's non-locality is a new unused tool and liability for protocol design and analysis.