  We study the complexity of computing the commuting-operator value $\omega^*$
of entangled XOR games with any number of players. We introduce necessary and
sufficient criteria for an XOR game to have $\omega^* = 1$, and use these
criteria to derive the following results:
  1. An algorithm for symmetric games that decides in polynomial time whether
$\omega^* = 1$ or $\omega^* < 1$, a task that was not previously known to be
decidable, together with a simple tensor-product strategy that achieves value 1
in the former case. The only previous candidate algorithm for this problem was
the Navascu\'{e}s-Pironio-Ac\'{i}n (also known as noncommutative Sum of Squares
or ncSoS) hierarchy, but no convergence bounds were known.
  2. A family of games with three players and with $\omega^* < 1$, where it
takes doubly exponential time for the ncSoS algorithm to witness this (in
contrast with our algorithm which runs in polynomial time).
  3. A family of games achieving a bias difference $2(\omega^* - \omega)$
arbitrarily close to the maximum possible value of $1$ (and as a consequence,
achieving an unbounded bias ratio), answering an open question of Bri\"{e}t and
Vidick.
  4. Existence of an unsatisfiable phase for random (non-symmetric) XOR games:
that is, we show that there exists a constant $C_k^{\text{unsat}}$ depending
only on the number $k$ of players, such that a random $k$-XOR game over an
alphabet of size $n$ has $\omega^* < 1$ with high probability when the number
of clauses is above $C_k^{\text{unsat}} n$.
  5. A lower bound of $\Omega(n \log(n)/\log\log(n))$ on the number of levels
in the ncSoS hierarchy required to detect unsatisfiability for most random
3-XOR games. This is in contrast with the classical case where the $n$-th level
of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all
possible solutions.
