Arnab Bhattacharyya: Algorithmic regularity for polynomials and applications

Friday, December 13, 2013 - 1:30pm to 2:30pm
MIT (Stata Center, Hewlett room, 32-G882)
Arnab Bhattacharyya
Indian Institute of Science

In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials given by Green and Tao and Kaufman and Lovett give a way of modifying a 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, 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/p−ε of some unknown polynomial of degree k over a prime field of order p (for k<d<p), then there is an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1−1/p−η 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 p).

Joint work with Pooya Hatami and Madhur Tulsiani.