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+arepsilon$ for arbitrarily small $arepsilon>0$. For values of q of the form $2^t-1$, the soundness error is $(q+1)/2^q+arepsilon$. Charikar, Makarychev, and Makarychev show that there is a constant $eta$ such that every language that has a verifier of query complexity q and a ratio of soundness error to completeness smaller than $eta 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/(logDelta)^alpha$ is Unique-Games-Hard for a certain constant $alpha>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.

Gowers uniformity, influence of variables, and PCPs

Trevisan, Luca
Membro del Collaboration Group
2009

Abstract

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+arepsilon$ for arbitrarily small $arepsilon>0$. For values of q of the form $2^t-1$, the soundness error is $(q+1)/2^q+arepsilon$. Charikar, Makarychev, and Makarychev show that there is a constant $eta$ such that every language that has a verifier of query complexity q and a ratio of soundness error to completeness smaller than $eta 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/(logDelta)^alpha$ is Unique-Games-Hard for a certain constant $alpha>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.
2009
Samorodnitsky, Alex; Trevisan, Luca
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11565/4035325
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 37
  • ???jsp.display-item.citation.isi??? 17
social impact