Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-035 | 23rd February 2020 01:56

No-Signaling MIPs and Faster-Than-Light Communication, Revisited


Authors: Justin Holmgren
Publication: 15th March 2020 08:28
Downloads: 816


We revisit one original motivation for the study of no-signaling multi-prover
interactive proofs (NS-MIPs): specifically, that two spatially separated
provers are guaranteed to be no-signaling by the physical principle that
information cannot travel from one point to another faster than light.

We observe that with more than two provers, the physical connection between
no-signaling and faster-than-light communication is more nuanced, depending on
the relative positioning of the provers. In particular, we observe that
provers are guaranteed to be no-signaling if and only if their positions are
convexly independent. Other prover positionings provide weaker guaranteees.

We consider a new issue that thus arises only in the many-prover setting:
how precisely must provers be positioned in order to guarantee the
soundness of a (NS-)MIP? We prove that substantially more precision is
required to guarantee full no-signaling than to guarantee soundness of a
specific NS-MIP for PSPACE implicit in the work of Kalai and Raz (CRYPTO 2009).

ISSN 1433-8092 | Imprint