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

DOI10.1137/20M1368598zbMATH Open1470.81023MaRDI QIDQ3387765FDOQ3387765

Authors: Thomas Vidick 

Publication date: 13 January 2021

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

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

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)

Cites Work

• Title not available (Why is that?)
• Non-deterministic exponential time has two-prover interactive protocols
• Three-player entangled XOR games are NP-hard to approximate
• Title not available (Why is that?)
• 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)

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)