Low-degree Testing or Distance to Reed-Solomon Codes

We consider the field Fq. Let f: Fq → Fq for which we only know a fraction of input and output. We suppose that q is large. We would like to give an answer to the following question: does there exist a polynomial of degree d which is very closed to the function f, and we would like to give an approximation of this distance, or equivalently, if we consider the smallest linear code of block length q − 1 containing both ev(f) and every codeword of the Reed-Solomon code [q − 1, d + 1]q we would like to give an approximation of the minimal distance between this last code and the Reed-Solomon code [q − 1, d+ 1]q. 1 Introduction, The Basic Univariate Test We want to test whether f is a polynomial of total degree d. M. Kiwi [2] describe equivalent tests that achieve this goal. Let Pd denote the set of polynomials from Fq to Fq of total degree d, and Cf (d) the smallest linear code of block length q − 1 containing both ev(f) and every codeword of the Reed-Solomon code C(d) = [q−1, d+1]q, Cf (d) def = {φev(f)+θg | g