Reducing the number of inputs in nonlocal games

Abstract

In this work we show how a vector-valued version of Schechtman's empirical method can be used to reduce the number of inputs in a nonlocal game $G$ while preserving the quotient $β^*(G)/β(G)$ of the quantum over the classical bias. We apply our method to the Khot-Vishnoi game, with exponentially many questions per player, to produce another game with polynomially many ($N\approx n^8$) questions so that the quantum over the classical bias is $Ω(n/\log^2 n)$.