  In analogy with the regularity lemma of Szemer\'edi, regularity lemmas for
polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by
Kaufman and Lovett (FOCS 2008) modify a given collection of polynomials \calF =
{P_1,...,P_m} to a new collection \calF' so that the polynomials in \calF' 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 \calF to \calF' 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 \calF'. In
particular, when the field is of high characteristic, in polynomial time, we
can refine \calF into \calF' where every nonzero linear combination of
polynomials in \calF' has desirably small Gowers norm.
  Using the algorithmic regularity lemmas, we show that if a polynomial P of
degree d is within (normalized) Hamming distance 1-1/|F| -\eps of some unknown
polynomial of degree k over a prime field F (for k < d < |F|), then there is an
efficient algorithm for finding a degree-k polynomial Q, which is within
distance 1-1/|F| -\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 (finding one close codeword), when the received word P itself is a
polynomial of degree d (with k < d < |F|).
  We also obtain an algorithmic version of the worst-case to average-case
reductions by Kaufman and Lovett. They show that if a polynomial of degree d
can be weakly approximated by a polynomial of lower degree, then it can be
computed exactly using a collection of polynomials of degree at most d-1. We
give an efficient (randomized) algorithm to find this collection.
