Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-116 | 12th October 2005 00:00

Gowers Uniformity, Influence of Variables, and PCPs



Gowers 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

ISSN 1433-8092 | Imprint