XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games

• URL: http://arxiv.org/abs/2607.06876v1
• Date: Wed, 08 Jul 2026 00:19:04 GMT
• Title: XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games
• Abstract summary: We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits.<n>We show that this dramatically increases the expressive power: the computational complexity of approximating the quantum value of tilted XOR games to constant precision is RE-complete.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.

Related papers

• Quantum non-local games: Quantum relations, projection lattices and rule operators [51.56484100374058]
  (mathcal R)-projection-test quantum games with finite-dimensional input and output von Neumann algebras.<n>(mathcal R)-projection-test quantum games with finite-dimensional input and output von Neumann algebras.<n>(mathcal R)-projection-test quantum games with finite-dimensional input and output von Neumann algebras.<n>(mathcal R)-projection-test quantum games with finite-dimensional input and output von Neumann algebras.
  arXiv  Detail & Related papers  (2026-08-31T09:41:14Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  We show that alternating RM$+$ converges to an $epsilon$-KKT point after $O_epsilon (1/epsilon4)$, establishing for the first time that it is a sound and fast first-order.<n>Our lower bound shows that convergence to coarse correlated equilibria in potential games is exponentially faster than convergence to Nash equilibria.
  arXiv  Detail & Related papers  (2025-10-20T00:45:47Z)
• Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, $\mathrm{XOR}^{*}$, compiled XOR, $\mathrm{XOR}^{*}$, and strong parallel repetiton of XOR, $\mathrm{XOR}^{*}$, and FFL games [0.0]
  We characterize exact, and approximate, optimality of games that players can interact with using quantum strategies.<n>We conclude this effort by describing other variants of other possible strategies, as proposed sources for quantum advantage.
  arXiv  Detail & Related papers  (2025-05-09T03:47:41Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover.<n>We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games [9.818381970014284]
  We show that the compiler proposed by Kalai et al. is sound for any two-player XOR game. Using our techniques, we obtain several additional results, including tight bounds on the compiled value of parallel-repeated XOR games.
  arXiv  Detail & Related papers  (2024-02-27T08:24:21Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  We present an incomplete-time approach to determining the winning regions of parity games via graph neural networks. It correctly determines the winning regions of $$60% of the games in our data set and only incurs minor errors in the remaining ones.
  arXiv  Detail & Related papers  (2022-10-18T15:10:25Z)
• Connecting XOR and XOR* games [0.0]
  We focus on two classes of games: XOR nonlocal games and XOR* sequential games with monopartite resources. We prove that under certain assumptions these two classes of games can be related via an explicit theorem that connects their optimal strategies.
  arXiv  Detail & Related papers  (2022-10-02T00:11:38Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time [0.0]
  We consider 3XOR games with perfect commuting operator strategies. We show existence of a perfect commuting operator strategy for the game can be decided in time.
  arXiv  Detail & Related papers  (2020-10-30T14:35:19Z)
• Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
  Subtraction games are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum games. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms.
  arXiv  Detail & Related papers  (2020-06-12T06:36:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.