scientific article; zbMATH DE number 7250157

DOI10.4230/LIPIcs.CCC.2018.17zbMath1441.68282MaRDI QIDQ5121905

Peter Manohar, Alessandro Chiesa, Igor Shinkar

Publication date: 22 September 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

linearity testingquasi-distributionsproperty testingnon-signaling strategies

Mathematics Subject Classification ID

Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

No-signaling linear PCPs ⋮ Unnamed Item ⋮ No-signaling linear PCPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Implausible consequences of superstrong nonlocality
• Non-deterministic exponential time has two-prover interactive protocols
• The physics of no-bit-Commitment: Generalized quantum non-locality versus oblivious transfer
• Self-testing/correcting with applications to numerical problems
• Improved low-degree testing and its applications
• On the power of non-local boxes
• On the Space Complexity of Linear Programming with Preprocessing
• Quantum Nonlocality and Beyond: Limits from Nonlocal Computation
• Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial
• Linearity testing in characteristic two
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Implications of superstrong non-locality for cryptography
• Derandomizing homomorphism testing in general groups
• Polynomial-Space Approximation of No-Signaling Provers
• Probabilistic checking of proofs
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Interactive proofs and the hardness of approximating cliques
• Robust Characterizations of Polynomials with Applications to Program Testing
• Analysis of Boolean Functions
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• How to delegate computations
• Direct Sum Testing
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
• Delegation for bounded space
• Bakerian Lecture - The physical interpretation of quantum mechanics

This page was built for publication: