Represent MOD function by low degree polynomial with unbounded one-sided error

Chris Beck, Yuan Li

In this paper, we prove tight lower bounds on the smallest degree of a nonzero polynomial in the ideal generated by $MO{D}_q$ or $\neg MO{D}_q$ in the polynomial ring $F_p[x_1, \ldots,…