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

Non-signaling strategies are a generalization of quantum strategies that havebeen studied in physics over the past three decades. Recently, they have foundapplications in theoretical computer science, including to provinginapproximability results for linear programming and to constructing protocolsfor delegating computation. A central tool for these applications isprobabilistically checkable proof (PCPs) systems that are sound againstnon-signaling strategies.  In this paper we show, assuming a certain geometrical hypothesis about noiserobustness of non-signaling proofs (or, equivalently, about robustness to noiseof solutions to the Sherali-Adams linear program), that a slight variant of theparallel repetition of the exponential-length constant-query PCP constructiondue to Arora et al. (JACM 1998) is sound against non-signaling strategies withconstant locality.  Our proof relies on the analysis of the linearity test and agreement test(also known as the direct product test) in the non-signaling setting.

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality