Posted

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\MIP^*=\RE with constant-length answers, we derive that \LIN1ϵ,s=\RE\LIN^*_{1-\epsilon,s}=\RE, for some 1/2<s<11/2< s<1 and for every sufficiently small ϵ>0\epsilon>0, where LIN refers to linearity (over F2\mathbb{F}_2) of the verifier predicate. Achieving the same result with ϵ=0\epsilon=0 would imply the existence of a non-hyperlinear group.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!