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

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

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

- +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