Paper Info
Title
Erratum: Three-Player Entangled Xor Games Are Np-Hard To Approximate
Abstract
This note indicates an error in the proof of Theorem 3.1 in [T. Vidick, SIAM J. Comput., 45 (2016), pp. 1007-1063]. Due to an induction step in the soundness analysis not being carried out correctly, the analysis fails to prove the claimed result. The error invalidates the proofs of the main computational hardness results claimed in the paper. We discuss implications for subsequent works. In some cases results can be partially recovered by applying a weakened version of Theorem 3.1 shown in [Z. Ji et al., Quantum Soundness of the Classical Low Individual Degree Test, arXiv:2009.1298, 2020] subsequently to the discovery of the error. The validity of Theorem 3.1 as stated in the paper remains an open question.
Year
DOI
Venue
2020
10.1137/20M1368598
SIAM JOURNAL ON COMPUTING
Keywords
DocType
Volume
quantum complexity, interactive proofs, nonlocal games
Journal
49
Issue
ISSN
Citations 
6
0097-5397
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Thomas Vidick137731.69