Using higher-order Fourier analysis over general fields

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

• For any fixed finite field $\mathbb{K}$, we show that the list decoding radius of the generalized Reed Muller code over $\mathbb{K}$ equals the minimum distance of the code. Previously, this had been proved over prime fields [BL14] and for the case when $\mathrm{\mid }\mathbb{K}\mathrm{\mid }-1$ divides the order of the code [GKZ08].
• For any fixed finite field $\mathbb{K}$, we give a polynomial time algorithm to decide whether a given polynomial $P:{\mathbb{K}}^n\to \mathbb{K}$ can be decomposed as a particular composition of lesser degree polynomials. This had been previously established over prime fields [Bha14, BHT15].
• For any fixed finite field $\mathbb{K}$, we prove that all locally characterized affine-invariant properties of functions $f: $\mathbb{K}$^n \to $\mathbb{K}$$aretestablewithone-sidederror\mathrm{.}Thesameresultwasknownwhen$$\mathbb{K}$$ is prime [BFHHL13] and when the property is linear [KS08]. Moreover, we show that for any fixed finite field $\mathbb{F}$, an affine-invariant property of functions $f:{\mathbb{K}}^n\to \mathbb{F}$, where $\mathbb{K}$ is a growing field extension over $\mathbb{F}$, is testable if it is locally characterized by constraints of bounded weight.