<p>If I understand your question correctly, <a href="http://eccc.hpi-web.de/report/2015/067/">the answer is no</a> (independently from the field, assuming $\mathsf{VP}\neq\mathsf{VNP}$).</p>

CC BY-SA 3.0
2015-08-07T19:35:02.170Z
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
CC BY-SA 3.0
2015-08-08T10:01:55.667Z
@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
CC BY-SA 3.0
2015-08-09T06:44:08.853Z
@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
CC BY-SA 3.0
2015-08-09T06:53:05.717Z
but minimal polynomial is always multilinear right? what is the point of considering higher degree f?
Turbo
CC BY-SA 3.0
2015-08-09T13:48:07.130Z
@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
CC BY-SA 3.0
2015-08-09T14:18:20.840Z
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
CC BY-SA 3.0
2015-08-07T13:58:30.240Z
2015-08-07T13:58:30.240Z
Bruno
<p>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$. </p>

<p>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}$). </p>

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

<p>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}$. </p>

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

<blockquote>
  <p>Can we bound $M(f)$ polynomially in terms of $C(f)$? </p>
</blockquote>

<p>Anything is known about this or something related? </p>

CC BY-SA 3.0
2015-08-06T18:33:21.103Z
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
CC BY-SA 3.0
2015-08-06T20:04:00.613Z
@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
CC BY-SA 3.0
2015-08-06T21:27:40.250Z
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
CC BY-SA 3.0
2015-08-06T22:13:12.690Z
How can a function over $\mathbb F_2$ not be multi-linear?
domotorp
CC BY-SA 3.0
2015-08-07T06:13:22.723Z
@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
CC BY-SA 3.0
2015-08-07T06:14:50.610Z
@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
CC BY-SA 3.0
2015-08-07T06:53:51.180Z
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
CC BY-SA 3.0
2015-08-07T07:05:01.037Z
@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
CC BY-SA 3.0
2015-08-07T08:21:03.957Z
I suppose $(\sum_i x_i)^{\frac n2}$ is a good candidate for separation.
domotorp
CC BY-SA 3.0
2015-08-07T09:04:41.347Z
@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
CC BY-SA 3.0
2015-08-07T11:15:39.077Z
I believe you but how could you do $(\sum_i x_i)^{\frac n2}$ in poly($n$)?
domotorp
CC BY-SA 3.0
2015-08-07T11:46:39.300Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/26696/discussion-between-gorav-jindal-and-domotorp).
Gorav Jindal
CC BY-SA 3.0
2015-08-08T18:40:35.637Z
Could I ask why $P_f$ of $f=(\sum_ix_i^2)$ is $n$ and $M_f$ is $n^2$?
Turbo
CC BY-SA 3.0
2015-08-09T06:40:30.247Z
@Turbo, it is not. We made a mistake, in this case both $M_f$ and $P_f$ are $O(n)$.
Gorav Jindal
<circuit-complexity><boolean-functions><polynomials>
Complexity of multi-linear polynomial computing Boolean function
Gorav Jindal
# Complexity of multi-linear polynomial computing Boolean function

(Asked by: username_0 on 2015-08-06)

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?

**Tags:** circuit-complexity, boolean-functions, polynomials

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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$.  
> **username_1**: 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?..  
> **username_2**: How can a function over $\mathbb F_2$ not be multi-linear?  
> **username_0**: @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.  
> **username_0**: @username_2, 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$?  
> **username_2**: 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?  
> **username_0**: @username_2, 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)$).  
> **username_2**: I suppose $(\sum_i x_i)^{\frac n2}$ is a good candidate for separation.  
> **username_0**: @username_2, 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.  
> **username_2**: I believe you but how could you do $(\sum_i x_i)^{\frac n2}$ in poly($n$)?  
> **username_0**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/26696/discussion-between-gorav-jindal-and-username_2).  
> **username_3**: Could I ask why $P_f$ of $f=(\sum_ix_i^2)$ is $n$ and $M_f$ is $n^2$?  
> **username_0**: @username_3, it is not. We made a mistake, in this case both $M_f$ and $P_f$ are $O(n)$.  

---

## 1 answers

### Answer by username_4 on 2015-08-07. Score: 7 | Accepted answer

If I understand your question correctly, [the answer is no](http://eccc.hpi-web.de/report/2015/067/) (independently from the field, assuming $\mathsf{VP}\neq\mathsf{VNP}$).

> **Comments:**
> **username_3**: 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\}$.  
> **username_3**: @username_4 I am unfamiliar with terminology for $f,\hat{f}$ in paper. Could you briefly tell what $\mathsf{VP\neq VNP}$ in this context?  
> **username_0**: @username_3, $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$.  
> **username_3**: but minimal polynomial is always multilinear right? what is the point of considering higher degree f?  
> **username_0**: @username_3, 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.  
> **username_3**: 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$?  

---

