Higher-order Fourier Analysis and Applications

Description

Introduction......Page 7 I Low Degree Testing......Page 9 Fourier analytic property testing......Page 13 Linearity Testing......Page 14 Testing for affine linearity......Page 15 Limitations of Fourier analysis......Page 16 Basic properties of low-degree polynomials......Page 17 Analysis of the AKKLR test......Page 19 Implications for the Gowers norms......Page 23 Low-degree Tests, the 1% Regime......Page 25 Soundness for d=1......Page 26 Soundness for d=2......Page 27 Gowers norms......Page 35 The counter-example......Page 36 U4-norm of S4......Page 37 Bounds on correlation with cubic polynomials......Page 38 II Higher Order Fourier Analysis......Page 41 Nonclassical Polynomials, and the Inverse Gowers Theorem......Page 45 Nonclassical polynomials......Page 46 The inverse theorem for Gowers norms......Page 47 Rank, Regularity, and Other Notions of Uniformity......Page 49 Polynomial factors......Page 50 Analytic measures of uniformity......Page 51 The derivative polynomial......Page 53 Regularization of factors......Page 55 Strong equidistribution of regular factors......Page 57 The joint distribution of high rank polynomials over linear forms......Page 59 Bias implies low rank approximation......Page 63 Bias implies low rank exact computation......Page 65 Basic decomposition theorem......Page 69 Higher-order Fourier expansion......Page 70 Strong decomposition theorems......Page 71 Sub-atom selection......Page 72 Homogeneous Nonclassical Polynomials......Page 75 A homogeneous basis for nonclassical polynomials......Page 76 A homogeneous basis, the univariate case......Page 77 A homogeneous basis, the multivariate case......Page 78 Cauchy-Schwarz complexity......Page 81 The true complexity......Page 83 Near-orthogonality: Proof of Theorem 7.6.1......Page 85 Proof of Theoren 11.2.4......Page 90 A lemma of Bogdanov and Viola......Page 94 Algorithmic Regularity Lemmas......Page 95 Algorithmic Inverse Theorem for Polynomials......Page 97 Derandomization via PRGs for Polynomials......Page 99 Algorithmic Decompositions......Page 100 III Algebraic Property Testing......Page 103 Locally Characterized Properties......Page 107 Subspace Hereditary Properties......Page 109 Locality Dimension......Page 110 Proof overview......Page 111 Big Picture Functions......Page 112 Proof of Testability......Page 113 Degree structural properties......Page 119 Proof of thm:degstruct......Page 120 Estimating the distance from algebraic properties......Page 123 Proof sketch of thm:distanceEstimableSubspace......Page 124 IV Open Problems......Page 129 Testing correlation with classical polynomials......Page 131 Norms defined by linear forms.......Page 132