Optimal strong parallel repetition for projection games on low threshold rank graphs

Given a two-player one-round game G with value val(G) = (1 - η), how quickly does the value decay under parallel repetition? If G is a projection game, then it is known that we can guarantee val(G ^⊗n ) ≤ (1 - η ² ) ^Ω(n) , and that this is optimal. An important question is under what conditions can we guarantee that strong parallel repetition holds, i.e. val(G ^⊗ ) ≤ (1 - η) ^Ω(n) ? In this work, we show a strong parallel repetition theorem for the case when G's constraint graph has low threshold rank. In particular, for any k ≥ 2, if σ _k is the k-th largest singular value of G's constraint graph, then we show that val(G ^⊗n ) ≤(1-√1-σ _k ² / k·η) ^Ω(n) . This improves and generalizes upon the work of [RR12], who showed a strong parallel repetition theorem for the case when G's constraint graph is an expander.