6

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?

Gorav Jindal
  • 727
  • 3
  • 10
  • Not sure that I understand the question. What's the difference between $P_f$ and $M_f$? By an arithmetic circuit you mean a circuit over {and,xor,1}, right? – Alexander S. Kulikov Aug 06 '15 at 18:33
  • 2
    @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$. – Gorav Jindal Aug 06 '15 at 20:04
  • I still don't understand. Can you give a toy function $f$ for which $P_f$ and $M_f$ are different? Also, if you have an arithmetic circuit computing $P_f$ or $M_f$ then it is also a circuit computing $f$, right?.. – Alexander S. Kulikov Aug 06 '15 at 21:27
  • How can a function over $\mathbb F_2$ not be multi-linear? – domotorp Aug 06 '15 at 22:13
  • 1
    @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. – Gorav Jindal Aug 07 '15 at 06:13
  • 1
    @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$? – Gorav Jindal Aug 07 '15 at 06:14
  • 1
    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? – domotorp Aug 07 '15 at 06:53
  • 1
    @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)$). – Gorav Jindal Aug 07 '15 at 07:05
  • I suppose $(\sum_i x_i)^{\frac n2}$ is a good candidate for separation. – domotorp Aug 07 '15 at 08:21
  • 1
    @domotorp, I would be surprised if we get unconditional separation because that would imply circuit lower bounds. I was hoping that either $M(f)$ is indeed polynomially bounded by $C(f)$ Or we can get some conditional lower bounds. – Gorav Jindal Aug 07 '15 at 09:04
  • I believe you but how could you do $(\sum_i x_i)^{\frac n2}$ in poly($n$)? – domotorp Aug 07 '15 at 11:15
  • Let us continue this discussion in chat. – Gorav Jindal Aug 07 '15 at 11:46
  • Could I ask why $P_f$ of $f=(\sum_ix_i^2)$ is $n$ and $M_f$ is $n^2$? – Turbo Aug 08 '15 at 18:40
  • @Turbo, it is not. We made a mistake, in this case both $M_f$ and $P_f$ are $O(n)$. – Gorav Jindal Aug 09 '15 at 06:40

1 Answers1

7

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

Bruno
  • 4,449
  • 33
  • 45
  • 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}$. – Turbo Aug 07 '15 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? – Turbo Aug 08 '15 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$. – Gorav Jindal Aug 09 '15 at 06:44
  • but minimal polynomial is always multilinear right? what is the point of considering higher degree f? – Turbo Aug 09 '15 at 06:53
  • @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. – Gorav Jindal Aug 09 '15 at 13:48
  • Questions: $(1)$ Over ${0,1}^n$ why would higher degree be any easier? $(2)$ Can you give an example? $(3)$ If you had 3SAT instance could you encode as $f$ or $\hat f$? – Turbo Aug 09 '15 at 14:18