TR05-116 Authors: Alex Samorodnitsky, Luca Trevisan

Publication: 13th October 2005 00:27

Downloads: 1295

Keywords:

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

polylog(D)/D.