Theoretical Computer Science
cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits
Updated Wed, 15 Jun 2022 09:23:12 GMT

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

Comments (5)

  • +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. — Mar 14, 2016 at 09:09  
  • +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  
  • +1 – 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?) — Mar 14, 2016 at 19:04  
  • +0 – @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.) — Mar 14, 2016 at 19:18  
  • +0 – Right. The author of a post is always notified of new comments, so the system removes the explicit @ notification as redundant. — Mar 15, 2016 at 11:35  

References