Loading...
Please wait, while we are loading the content...
Similar Documents
Gowers uniformity, influence of variables, and pcps (2005).
| Content Provider | CiteSeerX |
|---|---|
| Author | Samorodnitsky, Alex Trevisan, Luca |
| Description | This content is published in/by ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY, REPORT NO. 116 |
| Abstract | Gowers [Gow98, Gow01] introduced, for d ≥ 1, the notion of dimension-d uniformity U d (f) of a function f: G → C, where G is a finite abelian group. 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 = G1 × · · · × Gn as a product of groups. If a bounded balanced function f: G1 × · · · Gn → C is such that U d (f) ≥ ε, then one of the coordinates of f has influence at least ε/2O(d). Other inverse theorems are known [Gow98, Gow01, GT05, Sam05], and U 3 is especially well understood, but the properties of functions f with large U d (f), d ≥ 4, are not yet well characterized. The dimension-d Gowers inner product 〈{fS} 〉 U d of a collection {fS} S⊆[d] of functions is a related measure of pseudorandomness. The definition is such that if all the functions fS are equal to the same fixed function f, then 〈{fS} 〉 U d = U d (f). We prove that if fS: G1 × · · · × Gn → C is a collection of bounded functions such that 〈{fS} 〉 U d ≥ ε and at least one of the fS is balanced, then there is a variable that has influence at least ε2 /2O(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 ≥ 3 there is a PCP characterization of NP where the verifier makes q queries, has almost perfect completeness, and soundness at most 2q/2q. For infinitely many q, the soundness is (q + 1)/2q. 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/2k (or even (k + 1)/2k, for infinitely many k), and it is hard to approximate Independent Set in graphs of degree D within a factor (log D) O(1) /D. 1 |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Content Type | Text |
