Abstract
In analogy with the regularity lemma of Szemeredi, regularity lemmas for polynomials given by Green and Tao and Kaufman and Lovett give a way of modifying a given collection of polynomials F = {P_1,...,P_m} to a new collection F', so that the polynomials in F' are "pseudorandom." These lemmas have various applications, such as (special cases) of Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from F to F' is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection F'. In particular, when the field is of high characteristic, we can refine F into F' where every nonzero linear combination of polynomials in F' has desirably small Gowers norm.
Using the algorithmic regularity lemmas, we are able to obtain algorithmic versions of the above results. In particular, if a polynomial P of degree d is within (normalized) Hamming distance 1-1/p -\eps of some unknown polynomial of degree k over a prime field of order p (for k < d < p), then we give an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1-1/p -\eta of P, for some \eta depending on \eps. This can be thought of as decoding the Reed-Muller code of order k *beyond* the list decoding radius, in the sense of finding one close codeword, when the received word P itself is a polynomial (of degree larger than k but smaller than p).
Joint work with Pooya Hatami and Madhur Tulsiani.