ECCC-Report TR05-116https://eccc.weizmann.ac.il/report/2005/116Comments and Revisions published for TR05-116en-usThu, 13 Oct 2005 00:27:54 +0200
Paper TR05-116
| Gowers Uniformity, Influence of Variables, and PCPs |
Alex Samorodnitsky,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2005/116Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f)
of a function f: G -> \C, where G is a finite abelian group and \C are the
complex numbers. Roughly speaking, if a function has small Gowers uniformity
of dimension d, then it ``looks random'' on certain structured subsets of
the inputs.
We prove the following ``inverse theorem.'' Write G=G_1 x ... x G_n as a product of groups.
If a bounded balanced function f:G_1 x ... x G_n -> \C is such that U^{d} (f) > epsilon,
then one of the coordinates of f has influence at least epsilon/2^{O(d)}.
Other inverse theorems are known, and U^3 is especially well understood, but the
properties of functions f with large U^d(f), d\geq 4, are not yet well characterized.
The dimension-d Gowers inner product of a collection of functions is a related measure of
pseudorandomness. The definition is such that if all the functions in the collection
are equal to the same fixed function f, then their Gowers inner product equals U^d(f).
We prove that if a collection of bounded functions has dimension-d Gowers inner product
at least epsilon, and at least one of the functions is balanced, then there is a variable
that has influence at least epsilon^2/2^{O(d)} for at least four functions in the collection.
Finally, we relate the acceptance probability of the ``hypergraph long-code test'' proposed
by Samorodnitsky and Trevisan to the Gowers inner product of the functions being tested
and we deduce the following result: if the Unique Games Conjecture is true, then for every q\geq 3
there is a PCP characterization of NP where the verifier makes q queries, has almost perfect
completeness, and soundness at most 2q/2^q. For infinitely many q, the soundness is (q+1)/2^q.
Two applications of this results are that, assuming that the unique games conjecture is true,
it is hard to approximate Max kCSP within a factor 2k/2^k (or even (k+1)/2^k, for infinitely many k),
and it is hard to approximate Independent Set in graphs of degree $D$ within a factor
polylog(D)/D.
Thu, 13 Oct 2005 00:27:54 +0200https://eccc.weizmann.ac.il/report/2005/116