In analogy with the regularity lemma of Szemeredi, regularity lemmas for polynomials given by Green and Tao and by Kaufman and Lovett give a way of modifying a given collection F of polynomials to a new collection F', so that the polynomials in the new collection 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 allow for an efficient algorithm to compute the pseudorandom collection F'. We also prove that our notions suffice for the applications, for which the above regularity lemmas were proved.

Joint work with Arnab Bhattacharyya and Madhur Tulsiani.