Probabilistic checking against non-signaling strategies from linearity testing

DOI10.4230/LIPICS.ITCS.2019.25MaRDI QIDQ5090398zbMATH OpenFDO

Authors Alessandro Chiesa, Peter Manohar, Igor Shinkar

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2019.25

zbMATH Keywords

linearity testingnon-signaling strategiesprobabilistically checkable proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Recommendations

• Testing linearity against non-signaling strategies
• scientific article; zbMATH DE number 7250157
• No-signaling linear PCPs
• Polynomial-Space Approximation of No-Signaling Provers
• DELEGATING COMPUTATION VIA NO-SIGNALING STRATEGIES

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Computationally Sound Proofs
• Delegation for bounded space
• How to delegate computations
• scientific article; zbMATH DE number 7250157 (Why is no real title available?)
• Interactive proofs and the hardness of approximating cliques
• Linearity testing in characteristic two
• No-signaling linear PCPs
• Non-deterministic exponential time has two-prover interactive protocols
• On the space complexity of linear programming with preprocessing
• On zero-testable homomorphic encryption and publicly verifiable non-interactive arguments
• Polynomial-Space Approximation of No-Signaling Provers
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Self-testing/correcting with applications to numerical problems
• Succinct arguments from multi-prover interactive proofs and their efficiency benefits

Cited in

(4)

• Testing linearity against non-signaling strategies
• scientific article; zbMATH DE number 7250157 (Why is no real title available?)
• No-signaling linear PCPs
• No-signaling linear PCPs

This page was built for publication: Probabilistic checking against non-signaling strategies from linearity testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090398)