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 U^d(f) is small, then f has certain "pseudorandomness" properties. We prove the following property of functions with large U^d(f). 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)}. The Gowers inner product of a collection of functions is a related notion of pseudorandomness. We prove that if a collection of bounded functions has large Gowers inner product, and at least one function in the collection is balanced, then there is a variable that has high influence for at least four of the 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 applications to the construction of Probabilistically Checkable Proofs and to hardness of approximation.

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.