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 K , we show that the list decoding radius of the generalized Reed Muller code over K equals the minimum distance of the code. Previously, this had been proved over prime fields [BL14] and for the case when K − 1 divides the order of the code [GKZ08].

* For any fixed finite field K , we give a polynomial time algorithm to decide whether a given polynomial P : K n 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 K , we prove that all locally characterized affine-invariant properties of functions f : K n K are testable with one-sided error. The same result was known when K is prime [BFHHL13] and when the property is linear [KS08]. Moreover, we show that for any fixed finite field F , an affine-invariant property of functions f : K n F , where K is a growing field extension over F , is testable if it is locally characterized by constraints of bounded weight.