Gowers Uniformity, Influence of Variables, and PCPs

We study the relation of query complexity and soundness in probabilistically checkable proofs (PCPs). We present a PCP verifier for languages that are Unique-Games-Hard and such that the verifier makes $q$ queries, has almost perfect completeness, and has soundness error at most $2q/2^q+\varepsilon$ for arbitrarily small $\varepsilon0$. For values of $q$ of the form $2^t-1$, the soundness error is $(q+1)/2^q+\varepsilon$. Charikar, Makarychev, and Makarychev show that there is a constant $\beta$ such that every language that has a verifier of query complexity $q$ and a ratio of soundness error to completeness smaller than $\beta q/2^q$ is decidable in polynomial time. Up to the value of the multiplicative constant and to the validity of the Unique Games Conjecture, our result is therefore tight. As a corollary, we show that approximating the Maximum Independent Set problem in graphs of degree $\Delta$ within a factor better than $\Delta/(\log\Delta)^\alpha$ is Unique-Games-Hard for a certain constant $\alpha0$. Our main technical results are (i) a connection between the Gowers uniformity of a boolean function and the influence of its variables and (ii) the proof that “Gowers uniform” functions pass the “hypergraph linearity test” approximately with the same probability of a random function. The connection between Gowers uniformity and influence might have other applications.