Algorithmic regularity for polynomials and applications
Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani · 2013
In analogy with the regularity lemma of Szemerédi [Sze75], regularity lemmas for polynomials shown by Green and Tao [GT09] and by Kaufman and Lovett [KL08] give a way of modifying a given collection of polynomials F = {P1,..., Pm} 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, in polynomial time, 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 show that if a polynomial P of degree d is within (normalized) Hamming distance 1 − 1|F | − ε 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 | − η of P, for some η depending on ε. 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 |F|). We also obtain an algorithmic version of the worst-case to average-case reductions by Kauf-man and Lovett [KL08]. 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 polynomi-als of degree at most d − 1. We give an efficient (randomized) algorithm to find this collection.