Polynomial-Space Approximation of No-Signaling Provers

DOI10.1007/978-3-642-14165-2_13MaRDI QIDQ3587375zbMATH OpenOpenAlexFDO

Authors Tsuyoshi Ito

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14165-2_13

Mathematics Subject Classification ID

Applications of game theory (91A80) Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Signaling and communication in game theory (91A28)

Recommendations

• Non-signaling proofs with o(√ log n) provers are in PSPACE
• A k-provers parallel repetition theorem for a version of no-signaling model
• A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model
• Zero-knowledge proofs via polynomial representations
• scientific article; zbMATH DE number 4191107
• scientific article; zbMATH DE number 1487486
• Round-optimal zero-knowledge proofs of knowledge for NP
• Constant-Size Commitments to Polynomials and Their Applications
• scientific article; zbMATH DE number 4191124
• Precise zero-knowledge arguments with poly-logarithmic efficiency

Cited in

(12)

• Quantum de Finetti theorems under local measurements with applications
• scientific article; zbMATH DE number 7250157 (Why is no real title available?)
• Testing linearity against non-signaling strategies
• Constant-Size Commitments to Polynomials and Their Applications
• Interactive proofs with competing teams of no-signaling provers
• Arguments of proximity (extended abstract)
• Probabilistic checking against non-signaling strategies from linearity testing
• Bridging the gap between general probabilistic theories and the device-independent framework for nonlocality and contextuality
• A K-Provers Parallel Repetition Theorem for a Version of No-Signaling Model
• Interactive oracle proofs
• Parallel approximation of min-max problems
• Optimal non-signalling violations via tensor norms

This page was built for publication: Polynomial-Space Approximation of No-Signaling Provers

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