Erratum to: ``Three-player entangled XOR games are NP-hard to approximate

DOI10.1137/20M1368598MaRDI QIDQ3387765zbMATH OpenFDO

Authors Thomas Vidick

Publication date 13 January 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

quantum complexitynonlocal gamesinteractive proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Approximation algorithms (68W25) Quantum computation (81P68) Quantum measurement theory, state operations, state preparations (81P15) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) (n)-person games, (n>2) (91A06)

Recommendations

• Three-player entangled XOR games are NP-hard to approximate
• Entangled games are hard to approximate
• scientific article; zbMATH DE number 7250160
• Erratum for: ``On basing one-way functions on NP-hardness
• Explicit lower and upper bounds on the entangled value of multiplayer XOR games

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 7250160 (Why is no real title available?)
• 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
• Non-deterministic exponential time has two-prover interactive protocols
• Three-player entangled XOR games are NP-hard to approximate

Cited in

(1)

• Three-player entangled XOR games are NP-hard to approximate

This page was built for publication: Erratum to: ``Three-player entangled XOR games are NP-hard to approximate

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