2015/06/24 by Laura Mančinska, Mančinska, Laura, David E. Roberson +3 · 2 citations
Computer Science · Decision Sciences · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Game Theory and Applications #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1506.07429
openalex publication_date 2015/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
First, we consider the problem of deciding whether a nonlocal game admits a\nperfect entangled strategy that uses projective measurements on a maximally\nentangled shared state. Via a polynomial-time Karp reduction, we show that\nindependent set games are the hardest instances of this problem. Secondly, we\nshow that if every independent set game whose entangled value is equal to one\nadmits a perfect entangled strategy, then the same holds for all symmetric\nsynchronous games. Finally, we identify combinatorial lower bounds on the\nclassical and entangled values of synchronous games in terms of variants of the\nindependence number of appropriate graphs. Our results suggest that independent\nset games might be representative of all nonlocal games when dealing with\nquestions concerning perfect entangled strategies.\n