<p>The permanent would seem to qualify, at least conditionally (that is, assuming $\mathsf{VP}^0 \neq \mathsf{VNP}^0$). Note that the Boolean version of the permanent is just to decide whether a given bipartite graph has a perfect matching, which has poly-size circuits.</p>

<p>[Summarizing the comments below:] Despite this example being conditional, nothing more than a logarithmic gap can be expected unconditionally at the moment, since $\Omega(n \log n)$ is still the best known lower bound on general algebraic circuits. As pointed out by Stasys, this logarithmic gap is achieved by the function $\sum_{i=1}^n x_i^n$ (requires algebraic circuits of size $\Omega(n \log n)$ by Baur-Strassen), whose Boolean-ized version is just $x_1 \vee x_2 \vee \dotsb \vee x_n$.</p>

CC BY-SA 3.0
2016-03-14T09:09:26.847Z
Hi Joshua: you are right, permanent is an (albeit conditional) example! Well, we do not know any lower bound on A(f) for permanent. But if constant-free versions of VP and VNP  differ, then we know the separation B(f) vs. A(f) without knowing an (actual)  bound.
Stasys
CC BY-SA 3.0
2016-03-14T14:48:13.780Z
@Stasys: Note that even the "small gaps" that you asked for are unlikely to be known unconditionally, since the current best lower bound against a general algebraic circuit is only $\Omega(n \log n)$! So it's possible that there is a gap between a linear-size Boolean circuit and a quasi-linear algebraic lower bound, but nothing stronger is known unconditionally, and that's a *really* small gap...
Joshua Grochow
CC BY-SA 3.0
2016-03-14T19:04:13.863Z
at Joshua: right, good point again. If f is a sum of n-th powers of all n single variables, then B(f) is at most n, and Baur-Strassen show A(f) is at least about n times logarithm of n. This is the best known for A(f). So, the largest known *explicit* gap for my question is indeed only logarithmic. (A question aside: do you know why my @ always disappears in comments?)
Stasys
CC BY-SA 3.0
2016-03-14T19:18:55.500Z
@Stasys: Nice example. (Re: aside. I don't. I think the system does some automatic inference of who things are "at-ed" to, and if you are directing a message at the "default person", then it removes it. I think.)
Joshua Grochow
CC BY-SA 3.0
2016-03-15T11:35:58.683Z
Right. The author of a post is *always* notified of new comments, so the system removes the explicit @ notification as redundant.
Emil Jeřábek
CC BY-SA 3.0
2016-03-15T22:40:21.497Z
Thanks Emil and Josh: I got it this  "@ problem". The system is smart: it knows whom we speak to.
Stasys
CC BY-SA 3.0
2016-03-14T05:01:02.100Z
2016-03-14T19:17:32.823Z
2016-03-14T19:17:32.823Z
Joshua Grochow
<p>Let $A(f)$ denote the minimum size of a (non-monotone) arithmetic $(+,\times,-)$ circuit
computing a given multilinear  polynomial
$$
 f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,,
$$ 
 and $B(f)$ denote the minimum size of a (non-monotone) boolean $(\lor,\land,\neg)$ circuit
computing the<b> boolean version</b> $f_b$ of $f$ defined by:
$$
 f_b(x_1,\ldots,x_n)=\bigvee_{e\in E}\ \bigwedge_{i\colon e_i\neq 0} x_i\,.
$$</p>

<blockquote>
Are polynomials $f$ known for which $B(f)$ is smaller than $A(f)$?
</blockquote>

<p>If we consider <i>monotone</i> versions of circuits -- no Minus $(-)$ and no Not $(\neg)$ gates -- then $B(f)$ can be even <b>exponentially</b> smaller than $A(f)$: take, for example, the shortest s-t path polynomial $f$ on $K_n$;
then $B(f)=O(n^3)$ and $A(f)=2^{\Omega(n)}$. But what happens in the "non-monotone world"? Of course, <b>big</b> gaps cannot be known just because we do not have large lower bounds on $A(f)$. But perhaps there are at least some small gaps known? 
<hr>
NOTE (15.03.2016) In my question, I do not specified how large coefficients $c_e$ are allowed. Igor Sergeev remembered me that, for example, the following (univariate) polynomial $f(z)=\sum_{j=1}^m 2^{2^{jm}} z^j$ has $A(f)=\Omega(m^{1/2})$ (Strassen and people of his group). But $B(f)=0$ for this polynomial, since $f_b(z)=z$. We can obtain fron $f$ a <i>multivariate</i> polynomial $f'(x_1,\ldots,x_n)$
of $n=\log m$ variables using using Kronecker substitution. Associate with every exponent $j$ a monomial $X_j=\prod_{i:a_i=1}x_i$, where $(a_1,\ldots,a_n)$ are the 0-1 coefficients of the binary representation of $j$. Then the desired polynomial
is $f'=\sum_{j=1}^m c_j X_j$, and we have that 
$$
A(f')+n\geq  A(f)=\Omega(m^{1/2})=2^{\Omega(n)}.
$$ 
But the boolean version of $f'$ is just an OR of variables, so $B(f')\leq n-1$, and we have an even exponential gap. Thus, if magnitude of coefficients can be triple-exponential in the number $n$ of variables then the gap $A(f)/B(f)$ <b>can</b> be shown to be even exponential. (Actually, not the magnitude itself -- more the algebraic dependence of the coefficients.)
This is why the real problem with $A(f)$ is the case of <i>small</i> coefficients (ideally, only 0-1). But in this case, as Joshua recalled, the lower bound $A(f)=\Omega(n\log n)$ of Strassen and Baur (with 0-1 coefficients) remains the best what we have today. </p>

<cc.complexity-theory><circuit-complexity><lower-bounds><arithmetic-circuits>
Are arithmetic circuits weaker than boolean?
Stasys
# Are arithmetic circuits weaker than boolean?

(Asked by: username_0 on 2016-03-13)

Let $A(f)$ denote the minimum size of a (non-monotone) arithmetic $(+,\times,-)$ circuit
computing a given multilinear polynomial
$$
f(x\_1,\ldots,x\_n)=\sum\_{e\in E}c\_e\prod\_{i=1}^n x\_i^{e\_i}\,,
$$
and $B(f)$ denote the minimum size of a (non-monotone) boolean $(\lor,\land,\neg)$ circuit
computing the **boolean version** $f\_b$ of $f$ defined by:
$$
f\_b(x\_1,\ldots,x\_n)=\bigvee\_{e\in E}\ \bigwedge\_{i\colon e\_i\neq 0} x\_i\,.
$$

> Are polynomials $f$ known for which $B(f)$ is smaller than $A(f)$?

If we consider *monotone* versions of circuits -- no Minus $(-)$ and no Not $(\neg)$ gates -- then $B(f)$ can be even **exponentially** smaller than $A(f)$: take, for example, the shortest s-t path polynomial $f$ on $K\_n$;
then $B(f)=O(n^3)$ and $A(f)=2^{\Omega(n)}$. But what happens in the "non-monotone world"? Of course, **big** gaps cannot be known just because we do not have large lower bounds on $A(f)$. But perhaps there are at least some small gaps known?

---

NOTE (15.03.2016) In my question, I do not specified how large coefficients $c\_e$ are allowed. Igor Sergeev remembered me that, for example, the following (univariate) polynomial $f(z)=\sum\_{j=1}^m 2^{2^{jm}} z^j$ has $A(f)=\Omega(m^{1/2})$ (Strassen and people of his group). But $B(f)=0$ for this polynomial, since $f\_b(z)=z$. We can obtain fron $f$ a *multivariate* polynomial $f'(x\_1,\ldots,x\_n)$
of $n=\log m$ variables using using Kronecker substitution. Associate with every exponent $j$ a monomial $X\_j=\prod\_{i:a\_i=1}x\_i$, where $(a\_1,\ldots,a\_n)$ are the 0-1 coefficients of the binary representation of $j$. Then the desired polynomial
is $f'=\sum\_{j=1}^m c\_j X\_j$, and we have that
$$
A(f')+n\geq A(f)=\Omega(m^{1/2})=2^{\Omega(n)}.
$$
But the boolean version of $f'$ is just an OR of variables, so $B(f')\leq n-1$, and we have an even exponential gap. Thus, if magnitude of coefficients can be triple-exponential in the number $n$ of variables then the gap $A(f)/B(f)$ **can** be shown to be even exponential. (Actually, not the magnitude itself -- more the algebraic dependence of the coefficients.)
This is why the real problem with $A(f)$ is the case of *small* coefficients (ideally, only 0-1). But in this case, as Joshua recalled, the lower bound $A(f)=\Omega(n\log n)$ of Strassen and Baur (with 0-1 coefficients) remains the best what we have today.

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, arithmetic-circuits


---

## 1 answers

### Answer by username_1 on 2016-03-14. Score: 9 | Accepted answer

The permanent would seem to qualify, at least conditionally (that is, assuming $\mathsf{VP}^0 \neq \mathsf{VNP}^0$). Note that the Boolean version of the permanent is just to decide whether a given bipartite graph has a perfect matching, which has poly-size circuits.

[Summarizing the comments below:] Despite this example being conditional, nothing more than a logarithmic gap can be expected unconditionally at the moment, since $\Omega(n \log n)$ is still the best known lower bound on general algebraic circuits. As pointed out by username_0, this logarithmic gap is achieved by the function $\sum\_{i=1}^n x\_i^n$ (requires algebraic circuits of size $\Omega(n \log n)$ by Baur-Strassen), whose Boolean-ized version is just $x\_1 \vee x\_2 \vee \dotsb \vee x\_n$.

> **Comments:**
> **username_0**: Hi Joshua: you are right, permanent is an (albeit conditional) example! Well, we do not know any lower bound on A(f) for permanent. But if constant-free versions of VP and VNP  differ, then we know the separation B(f) vs. A(f) without knowing an (actual)  bound.  
> **username_1**: @username_0: Note that even the "small gaps" that you asked for are unlikely to be known unconditionally, since the current best lower bound against a general algebraic circuit is only $\Omega(n \log n)$! So it's possible that there is a gap between a linear-size Boolean circuit and a quasi-linear algebraic lower bound, but nothing stronger is known unconditionally, and that's a *really* small gap...  
> **username_0**: at Joshua: right, good point again. If f is a sum of n-th powers of all n single variables, then B(f) is at most n, and Baur-Strassen show A(f) is at least about n times logarithm of n. This is the best known for A(f). So, the largest known *explicit* gap for my question is indeed only logarithmic. (A question aside: do you know why my @ always disappears in comments?)  
> **username_1**: @username_0: Nice example. (Re: aside. I don't. I think the system does some automatic inference of who things are "at-ed" to, and if you are directing a message at the "default person", then it removes it. I think.)  
> **username_2**: Right. The author of a post is *always* notified of new comments, so the system removes the explicit @ notification as redundant.  
> **username_0**: Thanks Emil and Josh: I got it this  "@ problem". The system is smart: it knows whom we speak to.  

---

