Gowers Uniformity, Influence of Variables, and PCPs

Details Gowers Uniformity, Influence of Variables, and PCPs Gowers Uniformity, Influence of Variables, and PCPs

2005-10-12

arxiv.org/abs/math/0510264v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Gowers Uniformity, Influence of Variables, and PCPs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Gowers Uniformity, Influence of Variables, and PCPs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Gowers Uniformity, Influence of Variables, and PCPs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-470243