Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem

Abstract

We prove that for every 3-player (3-prover) game G with value less than one, whose query distribution has the support S = {(1,0,0), (0,1,0), (0,0,1)} of Hamming weight one vectors, the value of the n-fold parallel repetition G^{⊗n} decays polynomially fast to zero; that is, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every 3-player game G over binary questions and arbitrary answer lengths, with value less than 1, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Our proof technique is new and requires many new ideas. For example, we make use of the Level-k inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.