2005/10/12 by Alex Samorodnitsky, Samorodnitsky, Alex, Luca Trevisan +1 · 1 citation
Computer Science · #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.math/0510264
Gowers introduced, for d≥ 1, the notion of dimension-d uniformity Ud(f) of a function f: G -> \C, where G is a finite abelian group and \C are the complex numbers. Roughly speaking, if Ud(f) is small, then f has certain "pseudorandomness" properties. We prove the following property of functions with large Ud(f). Write G=G1 x >... x Gn as a product of groups. If a bounded balanced function f:G1 x ... x Gn -> \C is such that Ud (f) > epsilon, then one of the coordinates of f has influence at least epsilon/2O(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.