English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove a strong limitation on the ability of entangled provers to colludein a multiplayer game. Our main result is the first nontrivial lower bound onthe class MIP* of languages having multi-prover interactive proofs withentangled provers; namely MIP* contains NEXP, the class of languages decidablein non-deterministic exponential time. While Babai, Fortnow, and Lund(Computational Complexity 1991) proved the celebrated equality MIP = NEXP inthe absence of entanglement, ever since the introduction of the class MIP* itwas open whether shared entanglement between the provers could weaken orstrengthen the computational power of multi-prover interactive proofs. Ourresult shows that it does not weaken their computational power: MIP* containsMIP.  At the heart of our result is a proof that Babai, Fortnow, and Lund'smultilinearity test is sound even in the presence of entanglement between theprovers, and our analysis of this test could be of independent interest. As abyproduct we show that the correlations produced by any entangled strategywhich succeeds in the multilinearity test with high probability can always beclosely approximated using shared randomness alone.

A multi-prover interactive proof for NEXP sound against entangled provers