Higher-order Fourier Analysis and Applications

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