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 |\mathbb{K}|-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} are testable with one-sided error. The same result was known when \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.