# Can reciprocal inputs speed up monotone computations?

A $$(+,\times,1/x_i)$$ circuit is a standard monotone arithmetic $$(+,\times)$$ circuit with the only difference that now besides the input variables $$x_1,\ldots,x_n$$, also their reciprocals $$1/x_1,\ldots,1/x_n$$ can be used as inputs.

That the gap (A) can be exponential was recently shown by Fomin, Grigoriev and Koshevoy: using ideas from electric network theory, they designed a $$(+,\times,/)$$ circuits of size $$O(n^3)$$ computing the generating polynomial of spanning trees of $$n$$-vertex graphs. This result is quite interesting: more than 35 years ago, Strassen has shown that division $$(/)$$ is useless, if we have subtraction $$(-)$$ in our disposal. So, an intact division taste on our calculator can still help, if the subtraction $$(-)$$ taste is long broken.

Thus, we now know that at least one of the gaps (B) and (C) must be exponential, but we do not know which.

Question 1: Can the gap (C) be exponential? That is, can the presence of reciprocal inputs $$1/x_i$$ substantially decrease the size of $$(+,\times)$$ circuits?

This question is related to the following question concerning the $$(+,\times)$$ complexity of polynomials and their "complements". Define the complement of a multilinear polynomial $$f(x) = \sum_{S\in{\cal F}}\prod_{i\in S}x_i$$ to be the multilinear polynomial co-$$f = \sum_{S\in{\cal F}}\prod_{i\not\in S}x_i$$. That is, monomials of co-$$f$$ are just complements of monomials of $$f$$.

Question 2: Can a polynomial $$f$$ require super-polynomially larger monotone arithmetic $$(+,\times)$$ circuits than its complement co-$$f$$?

An affirmative answer to Q2 would also answer Q1 in the affirmative: If the complement co-$$f$$ of an $$n$$-variate polynomial $$f$$ can be computed by a $$(+,\times)$$ circuit of size $$s$$, then $$f$$ can be computed by a $$(+,\times,1/x_i)$$ circuit of size $$s+n$$. To show this, suppose the complement co-$$f(x) = \sum_{S\in{\cal F}}\prod_{i\not\in S}x_i$$ has a $$(+,\times)$$ circuit $$F(x)$$ of size $$s$$. If we replace each input variable $$x_i$$ by its reciprocal $$y_i=1/x_i$$, then the obtained $$(+,\times,1/x_i)$$ circuit $$F'$$ computes a rational function of the form $$f' =\sum_{S\in{\cal F}}\prod_{i\not\in S}y_i =\sum_{S\in{\cal F}}\prod_{i\not\in S}\frac{1}{x_i}$$. If we take the monomial $$M=x_1x_2\cdots x_n$$, then the $$(+,\times,1/x_i)$$ circuit $$M\cdot F'$$ of size $$s+n$$ computes our original polynomial $$M\cdot f'=f$$.

Note 1: If instead of arithmetic $$(+,\times)$$ circuits we consider boolean $$(\lor,\land)$$ circuits, then the answer to Question 2 is YES: then the gap can be super-polynomial. Note that the complement co-$$f$$ of a monotone boolean function $$f$$ is neither its negation $$\neg f$$ nor its dual $$\neg f(\neg x)$$: minterms of co-$$f$$ are complements of the minterms of $$f$$.

To show the gap, consider the logical permanent function $$\mathrm{Per}(x)$$. This function has $$n^2$$ variables $$x_e$$, one for each edge of the complete bipartite $$n\times n$$ graph $$K_{n,n}$$. The function is an OR of $$n!$$ minterms, each corresponding to a perfect matching in $$K_{n,n}$$. Consider the boolean function $$g$$ on the same variables such that $$g(x)=1$$ iff the graph $$G_x$$ specified by $$x$$ is the complement of some (not necessarily perfect) matching. This happens iff every vertex of $$K_{n,n}$$ has degree $$\geq n-1$$ in $$G_x$$. This latter condition can be easily verified by a $$(\lor,\land)$$ circuit of size $$O(n^4)$$. Since the minterms of $$g$$ are complements of perfect matchings, $$g$$ is the complement co-$$\mathrm{Per}$$ of the permanent function. Thus, co-$$\mathrm{Per}$$ can be computed by a $$(\lor,\land)$$ circuit of size $$O(n^4)$$ but, as shown by Razborov, the function $$\mathrm{Per}$$ itself requires such circuits of size $$n^{\Omega(\log n)}$$. The reason why this argument does not answer Q2 in the arithmetic $$(+,\times)$$ case is that then all terms, not just shortest ones, do matter. So, then the polynomial $$g$$ does not compute the polynomial co-$$\mathrm{Per}$$.

Note 2: The weakness of arithmetic $$(+,\times)$$ circuits, in contrast to boolean $$(\lor,\land)$$ circuits, comes from them being unable to remove anything they produce under the way. Tropical $$(\min,+)$$ and $$(\max,+)$$ circuits (working over all nonnegative real numbers) constitute an intermediate model between boolean and arithmetic. They already can remove things via $$\min(x,x+y)=x$$ and $$\max(x,x+y)=x+y$$. So, perhaps Question 2 can be answered in the affirmative for tropical circuits? Note that over tropical $$(\min,+)$$ and $$(\max,+)$$ semirings, division $$(/)$$ corresponds to subtraction $$(-)$$. So, the corresponding chart (in the case of minimization) is:

That the gap (A) is exponential follows from the above mentioned upper bound $$O(n^3)$$ on the $$(\min,+,-)$$ circuit complexity of the MST problem (minimum weight spanning tree problem), and known exponential lower bounds on the $$(\min,+)$$ circuit complexity of MST, both for directed and undirected graphs.

I believe the answer to the Question 1 is negative.

We introduce an auxiliary circuit type: $$X_k$$-circuits have inputs $$x_1, \dots, x_n$$ and $$1/x_k,\dots,1/x_n$$ and have in addition to $$+$$ and $$\times$$ gates unary gates multiplying the input by $$x_i^p$$ for $$i < k$$, $$p > 0$$. $$X_1$$-circuits are monotone circuits with all reciprocal inputs, and $$X_{n+1}$$-circuits have no reciprocal inputs, but have multiplications by power of every monomial.

We transform an $$X_k$$-circuit computing a polynomial $$F$$ into an $$X_{k + 1}$$-circuit.

Each gate $$g$$ computes a Laurent polynomial $$P_g$$. Represent it as $$P_g = x_k^{e_g} Q_g / M_g$$ where $$Q_g$$ and $$M_g$$ are not divisible by $$x_k$$. We will transform the circuit in such a way that the corresponding gate in the transformed circuit computes $$Q_g / M_g$$.

Multiplication gates and multiplications by variable powers do not change. For addition $$x_k^e Q / M = x_k^{e_1} Q_1 / M_1 + x_k^{e_2} Q_2 / M_2$$ we will have $$e = \min \{e_1, e_2\}$$. W.l.o.g. $$e_1 = e$$, $$e_2 = e + d$$. Replace the addition gate by one addition and one power multiplication: $$Q/M = Q_1 / M_1 + x_k^d Q_2 / M_2$$.

In the end multiply the final result by appropriate power of $$x_k$$ if needed to get the required $$F$$.

In this way we transform an $$X_k$$-circuit with $$a$$ additions, $$m$$ multiplications and $$p$$ power-multiplications into an $$X_{k + 1}$$-circuit with $$a$$ additions, $$m$$ multiplications and at most $$p + a + 1$$ power-multiplications.

Doing this $$n$$ times to an $$X_1$$-ciruit with $$a$$ additions and $$m$$ multiplications we get a $$X_{n + 1}$$-circuit with $$a$$ additions, $$m$$ multiplications and at most $$n(a + 1)$$ power multiplications.

As Stasys notes in the comments, all powers involved are at most $$2^m$$, so we need at most $$(a + 2)m$$ multiplications to implement all $$(a + 1)$$ required powers of one variable. So we transformed a circuit with reciprocals with $$a$$ additions and $$m$$ multiplications into a circuit without reciprocals with $$a$$ additions and $$m + n m (a + 2)$$ multiplications.

• Right, we can easily construct a circuit $C$ computing even the pair $(Q,M)$ such that $Q=F\cdot M$ (not just a circuit for the product polynomial $F\cdot M$). But how (even knowing $M$) to turn C into a circuit C' computing F? I mean: without cancellations at single gates, which is the essence of reciprocal inputs $1/x_i$? – Stasys Aug 15 '19 at 12:23
• In my old draft notices, I've now found how to get C' from C. If correct the resulting size is then $n\cdot s^2$, where $s$ is the size of C. I used the fact that no variable can appear in the monomial $M$ with degree larger than $2^s$. And yes, I also used gcd, albeit in terms of Minkowski $(\cup,+)$ circuits (producing the sets of exponent vectors of polynomials), not arithmetic $(+,\times)$ circuits, but this is only a notational issue. So, if you see some much simpler way to get C' from C, this would be interesting. – Stasys Aug 15 '19 at 12:46
• You are right, I did miss the fact that if we use an input in multiple gates, the monomials are different. We can multiply it by different monomials, increasing the size. $ns^2$ seems to be the right number of additional gates. My construction only works for formulas. – Vladimir Lysikov Aug 15 '19 at 13:27
• @Stasys Check out the edited answer, this is another way to present it. But it is likely the same construction you have. – Vladimir Lysikov Aug 15 '19 at 14:37
• Yes, my proof in old notes was similar, but more "global" (with a goal to show the same also for topical circuits). But your idea to eliminate reciprocal inputs one-by-one is just nice! So, under proviso that "substantially" means "more than quadraticaly", both my questions are answered. – Stasys Aug 27 '19 at 6:33