Theoretical Computer Science

# Are arithmetic circuits weaker than boolean?

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.

## Solution

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 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$.

• +2 – @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... — Mar 14, 2016 at 14:48