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/

Zendy Plus

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

Zendy Tools

Zendy Open

Non-signaling proofs, motivated by quantum computation, have foundapplications in cryptography and hardness of approximation. An important openproblem is characterizing the power of no-signaling proofs. It is known that2-prover no-signaling proofs are characterized by PSPACE, and that no-signalingproofs with $poly(n)$-provers are characterized by EXP. However, the power of$k$-prover no-signaling proofs, for $2<k<poly(n)$ remained an open problem.  We show that $k$-prover no-signaling proofs (with negligible soundness) for$k=O(\sqrt{\log n})$ are contained in PSPACE. We prove this via two differentroutes that are of independent interest. In both routes we consider arelaxation of no-signaling called sub-no-signaling. Our main technicalcontribution (which is used in both our proofs) is a reduction showing how toconvert any sub-no-signaling strategy with value at least $1-2^{-\Omega(k^2)}$into a no-signaling one with value at least $2^{-O(k^2)}$.  In the first route, we show that the classical prover reduction method forconverting $k$-prover games into $2$-prover games carries over to theno-signaling setting with the following loss in soundness: if a $k$-player gamehas value less than $2^{-ck^2}$ (for some constant~$c>0$), then thecorresponding 2-prover game has value at most $1 - 2^{dk^2}$ (for someconstant~$d>0$). In the second route we show that the value of asub-no-signaling game can be approximated in space that is polynomial in thecommunication complexity and exponential in the number of provers.

Non-Signaling Proofs with $O(\sqrt{\log n})$ Provers are in PSPACE