scientific article; zbMATH DE number 7250160

DOI10.4230/LIPICS.CCC.2018.20zbMATH Open1441.68079arXiv1710.03062MaRDI QIDQ5121908FDOQ5121908

Authors: Anand Natarajan, Thomas Vidick 

Publication date: 22 September 2020

Full work available at URL: https://arxiv.org/abs/1710.03062

Title of this publication is not available (Why is that?)

Recommendations

• Entangled games are hard to approximate
• Three-player entangled XOR games are NP-hard to approximate
• Unique games with entangled provers are easy
• Parallel repetition of entangled games
• Quantum XOR games

zbMATH Keywords

multi-prover interactive proof systemslow-degree testingentangled nonlocal games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68) 2-person games (91A05)

Cites Work

• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• Proof verification and the hardness of approximation problems
• Monogamy of non-local quantum correlations
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• Title not available (Why is that?)
• Some optimal inapproximability results
• Self-testing/correcting with applications to numerical problems
• Non-deterministic exponential time has two-prover interactive protocols
• How to delegate computations
• Algebraic methods for interactive proof systems
• IP = PSPACE
• A parallel repetition theorem for entangled projection games
• Delegating computation: interactive proofs for muggles
• Classical verification of quantum proofs
• A quantum linearity test for robustly verifying entanglement
• A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)

Cited In (11)

• Unique games with entangled provers are easy
• Spatial Isolation Implies Zero Knowledge Even in a Quantum World
• Title not available (Why is that?)
• Entangled games are hard to approximate
• Hardness amplification for entangled games via anchoring
• Characterization of binary constraint system games
• Erratum to: ``Three-player entangled XOR games are NP-hard to approximate
• Geometry of information structures, strategic measures and associated stochastic control topologies
• Quantum free games
• Three-player entangled XOR games are NP-hard to approximate
• Title not available (Why is that?)

This page was built for publication:

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