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

Abstract

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,\dots ,x_n]/(x_1^2=x_1,\dots ,x_n^2=x_n)$, $p,q$ are coprime, which is called \emph{immunity} over $F_p$. The immunity of $MO{D}_q$ is lower bounded by $\lfloor (n+1)/2\rfloor$, which is achievable when $n$ is a multiple of $2q$; the immunity of $\neg MO{D}_q$ is exactly $\lfloor (n+q-1)/q\rfloor$ for every $q$ and $n$. Our result improves the previous bound $\lfloor \frac{n}{2(q-1)}\rfloor$ by Green. We observe how immunity over $F_p$ is related to $\acc$ circuit lower bound. For example, if the immunity of $f$ over $F_p$ is lower bounded by $n/2-o(\sqrt{n})$, and $|1_f|=\Omega (2^n)$, then $f$ requires $\acc$ circuit of exponential size to compute.

Cited by in corpus (1)

• Integer Addition and Hamming Weight