Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

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

Justin Holmgren

Published Jan 1, 2020• 1 citation
OpenAlex

Related papers

CP violation does not make faster-than-light communication possible

J. Finkelstein, Henry Pierce Stapp

Physics Letters A•Dec 1, 1987•17 citations

Faster than Light Communication

Vijay Raj Franklin P.

International Conference on Computer Applications (ICCA)•Jan 1, 2010•0 citations

On a Recent Proposal of Faster than Light Quantum Communication

Angelo Bassi, G. C. Ghirardi

arXiv:0711.4538•International Journal of Theoretical Physics•Mar 12, 2008•7 citations

How to Delegate Computations: The Power of No-Signaling Proofs

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t = t ( n ), where the running time of the prover is poly ( t ) and the running time of the verifier is n · polylog ( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval ( PIR ) scheme. 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 ), we construct a multi-prover interactive proof ( MIP ), that is, sound against no-signaling strategies, where the running time of the provers is poly ( t ), the number of provers is polylog ( t ), and the running time of the verifier is n · polylog ( t ). In particular, this shows that the class of languages that have polynomial-time MIP s that are sound against no-signaling strategies, is exactly EXP . Previously, this class was only known to contain PSPACE . To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.

Journal of the ACM•Nov 29, 2021•18 citations

Parallel repetition of MIP(2,1) systems

Clemens Gröpl, Martin Skutella

Lecture notes in computer science•Jan 1, 1998•0 citations

New Directions for High-throughput and High-security Communication.

Adrian Perrig

•Jan 1, 2021•0 citations
We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t = t ( n ), where the running time of the prover is poly ( t ) and the running time of the verifier is n · polylog ( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval ( PIR ) scheme. 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 ), we construct a multi-prover interactive proof ( MIP ), that is, sound against no-signaling strategies, where the running time of the provers is poly ( t ), the number of provers is polylog ( t ), and the running time of the verifier is n · polylog ( t ). In particular, this shows that the class of languages that have polynomial-time MIP s that are sound against no-signaling strategies, is exactly EXP . Previously, this class was only known to contain PSPACE . To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.