6
$\begingroup$

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?

Improve this question
$\endgroup$
14
  • 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
    Commented Aug 6, 2015 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
    Commented Aug 7, 2015 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
    Commented Aug 7, 2015 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
    Commented Aug 7, 2015 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
    Commented Aug 7, 2015 at 7:05

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\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
    Commented Aug 7, 2015 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
    Commented Aug 8, 2015 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
    Commented Aug 9, 2015 at 6:44
  • $\begingroup$ but minimal polynomial is always multilinear right? what is the point of considering higher degree f? $\endgroup$
    – Turbo
    Commented Aug 9, 2015 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
    Commented Aug 9, 2015 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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