Gowers uniformity, influence of variables, and PCPs
A Samorodnitsky, L Trevisan - Proceedings of the thirty-eighth annual …, 2006 - dl.acm.org
A Samorodnitsky, L Trevisan
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, 2006•dl.acm.orgWe return to the study of the relation of query complexity and soundness in probabilistically
checkable proofs. 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/2q+ ε, for arbitrarily small ε> 0. For values of q of the form 2t-1,
the soundness error is (q+ 1)/2q+ ε. Charikar et al. show that there is a constant c such that
for every language that has a verifier of query complexity q, and a ratio of soundness error to …
checkable proofs. 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/2q+ ε, for arbitrarily small ε> 0. For values of q of the form 2t-1,
the soundness error is (q+ 1)/2q+ ε. Charikar et al. show that there is a constant c such that
for every language that has a verifier of query complexity q, and a ratio of soundness error to …
We return to the study of the relation of query complexity and soundness in probabilistically checkable proofs.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/2q+ε, for arbitrarily small ε>0. For values of q of the form 2t-1, the soundness error is (q+1)/2q+ε.Charikar et al. show that there is a constant c such that for every language that has a verifier of query complexity q, and a ratio of soundness error to completeness smaller than cq/2q 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 Δ within a factor better than Δ/(log Δ)c is Unique-Games-Hard for a certain constant c>0.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.

Showing the best result for this search. See all results