13
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Stasys Mar 14 '16 at 9:09
  • 2
    $\begingroup$ @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... $\endgroup$ – Joshua Grochow Mar 14 '16 at 14:48
  • 1
    $\begingroup$ 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?) $\endgroup$ – Stasys Mar 14 '16 at 19:04
  • $\begingroup$ @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.) $\endgroup$ – Joshua Grochow Mar 14 '16 at 19:18
  • $\begingroup$ Right. The author of a post is always notified of new comments, so the system removes the explicit @ notification as redundant. $\endgroup$ – Emil Jeřábek Mar 15 '16 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.