Aviv Taller, Thomas Vidick (Jul 31 2025).
Abstract: We generalize Håstad's long-code test for projection games and show that it remains complete and sound against entangled provers. Combined with a result of Dong et al. \citeDong25, which establishes that
\MIP∗=\RE with constant-length answers, we derive that
\LIN1−ϵ,s∗=\RE, for some
1/2<s<1 and for every sufficiently small
ϵ>0, where LIN refers to linearity (over
F2) of the verifier predicate. Achieving the same result with
ϵ=0 would imply the existence of a non-hyperlinear group.