# Complexity of multi-linear polynomial computing Boolean function

Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual, let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest Boolean circuit computing $f$.

As we know that every Boolean function can be computed by polynomials in $\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$. Let $P(f)$ be the size of the smallest arithmetic circuit(over $\mathbb{F}_{2}$) which computes a polynomial $P_{f}$ such that $P_{f}$ computes the same function as $f$ on $\mathbb{F}_{2}^{n}$(correspondingly $\{0,1\}^{n}$).

It is known that $P(f)\leq\textrm{poly}(C(f))$ and $C(f)\leq\textrm{poly}(P(f))$.

We also know that there is a unique multi-linear polynomial $M_f\in\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$ such that $M_{f}$ computes the same function as $f$ on $\mathbb{F}_{2}^{n}$(correspondingly $\{0,1\}^{n}$). Let $M(f)$ be the size of the smallest arithmetic circuit(over $\mathbb{F}_{2}$) computing $M_{f}$.

It is clear that $C(f)\leq\textrm{poly}(M(f))$. How about other direction?

Can we bound $M(f)$ polynomially in terms of $C(f)$?

• @AlexanderS.Kulikov, $P_f$ might not be multi-linear and $M_f$ has to be necessarily multi-linear. By an arithmetic circuit, I mean a straight line program over $\mathbb{F}_2$. You can think of this circuit as {and,xor,1} if you want because multiplication is "and" and addition is "xor" over $\mathbb{F}_2$. Aug 6, 2015 at 20:04
• @AlexanderS.Kulikov,For example, $P_{f}$ might be $x_{1}^{5}x_{2}^{4}+x_{3}^{2}x_{4}^{2}$ and then $M_{f}$ will be $x_{1}x_{2}+x_{3}x_{4}$. Both $P_{f}$ and $M_{f}$ compute the same function $f$ over $\mathbb{F}_{2}^{4}$(hence over $\{0,1\}^{4}$) but they are different polynomials. Aug 7, 2015 at 6:13
• @domotorp, I agree with you. Any function $f$ over $\mathbb{F}_{2}^{n}$ is represented by a unique multi-linear polynomial $M_{f}$. What I am asking is that if we can bound the size of the smallest arithmetic circuit computing $M_{f}$ in terms of Boolean circuit complexity of $f$? Aug 7, 2015 at 6:14
• I think I understand. For example, if $f=(\sum_i x_i)^2$, we would have $P_f\approx n$ but (most probably) $M_f\approx n^2$, right? Aug 7, 2015 at 6:53
• @domotorp, yeah in the example you gave, $P_f$ is $O(n)$ but most likely $M_f$ is $\omega(n)$ (you feel that it is $\Omega(n^2)$). Aug 7, 2015 at 7:05

If I understand your question correctly, the answer is no (independently from the field, assuming $\mathsf{VP}\neq\mathsf{VNP}$).
• There are two objects here $f$ and $\hat{f}$. Is $\hat{f}$ multilinear over $\Bbb R$? How about $f$? I really do not understand how $f$ and $\hat{f}$ can be different if both domain and range of interest is from alphabet $\{0,1\}$. Aug 7, 2015 at 19:35
• @Bruno I am unfamiliar with terminology for $f,\hat{f}$ in paper. Could you briefly tell what $\mathsf{VP\neq VNP}$ in this context? Aug 8, 2015 at 10:01
• @Turbo, $f$ is any polynomial agreeing with given function on $\{0,1\}^n$, $f$ does not need to be multi-linear. Whereas $\hat{f}$ is the unique multi-linear polynomial agreeing with given function on $\{0,1\}^n$. Aug 9, 2015 at 6:44
• @Turbo, higher degree $f$ might be easier to compute. This is exactly what this paper pointed by bruno shows, that higher degree $f$ is in $\mathsf{VP}$ whereas $\hat{f}$ is $\mathsf{VNP}$-complete. Aug 9, 2015 at 13:48