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)$?

Anything is known about this or something related?

  • 2
    $\begingroup$ @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$. $\endgroup$ – Gorav Jindal Aug 6 '15 at 20:04
  • 1
    $\begingroup$ @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. $\endgroup$ – Gorav Jindal Aug 7 '15 at 6:13
  • 1
    $\begingroup$ @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$? $\endgroup$ – Gorav Jindal Aug 7 '15 at 6:14
  • 1
    $\begingroup$ 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? $\endgroup$ – domotorp Aug 7 '15 at 6:53
  • 1
    $\begingroup$ @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)$). $\endgroup$ – Gorav Jindal Aug 7 '15 at 7:05

If I understand your question correctly, the answer is no (independently from the field, assuming $\mathsf{VP}\neq\mathsf{VNP}$).

  • $\begingroup$ 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\}$. $\endgroup$ – Turbo Aug 7 '15 at 19:35
  • $\begingroup$ @Bruno I am unfamiliar with terminology for $f,\hat{f}$ in paper. Could you briefly tell what $\mathsf{VP\neq VNP}$ in this context? $\endgroup$ – Turbo Aug 8 '15 at 10:01
  • $\begingroup$ @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$. $\endgroup$ – Gorav Jindal Aug 9 '15 at 6:44
  • $\begingroup$ but minimal polynomial is always multilinear right? what is the point of considering higher degree f? $\endgroup$ – Turbo Aug 9 '15 at 6:53
  • $\begingroup$ @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. $\endgroup$ – Gorav Jindal Aug 9 '15 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.