# Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?

I'm new to circuit complexity, and trying to understand Hyafil's decomposition theorem (Theorem 1 in , Lemma 3 in , Decomposition Lemma in , also mentioned in ). My question is: Is homogeneity required if we apply this theorem to monotone circuits (i.e. circuits that compute over the semiring of non-negative reals)?

The statement of the theorem is: Let $$f$$ be a polynomial of degree $$deg(f)$$ computed by an arithmetic circuit** with $$t$$ gates. The polynomial $$f$$ can be written as $$f = g_1 \cdot h_1 + \ldots + g_t \cdot h_t$$, where $$deg(g_i) \le 2deg(f)/3$$ and $$deg(h_i) \le 2deg(f)/3$$.

** with some restrictions

This theorem is proved by repeatedly finding a gate $$v$$ that computes a polynomial $$f_v$$ where $$deg(f)/3 \le deg(f_v) \le 2deg(f)/3$$ and writing the polynomial as $$f = f_v \cdot h + f_{v=0}$$, where $$h$$ is some polynomial that must be of degree at most $$2deg(f)/3$$ and $$f_{v=0}$$ is the polynomial obtained by setting the gate $$v$$ to zero.

All statements of this theorem that I have seen require homogeneity of the circuit, which I guess is required for non-monotone circuits. However, to my understanding of the proof it should also work for non-homogeneous monotone circuits. (It should work when for polynomials $$g$$ and $$h$$ it holds that $$deg(g+h) = \max(deg(g), deg(h))$$ and $$deg(g \cdot h) = deg(g) + deg(h)$$.) Am I missing something?

 Hyafil, L. (1979). On the parallel evaluation of multivariate polynomials. SIAM Journal on Computing, 8(2), 120-123.

 Valiant, L. G. (1979, April). Negation can be exponentially powerful. In Proceedings of the eleventh annual ACM symposium on Theory of computing (pp. 189-196).

No, homogeneity is not required when applying this theorem to monotone circuits, and in fact homogeneity is a quite technical restriction that can be removed even in the general case by weakening the theorem a bit. I'll try to explain some things that made this more clear to me. (and hopefully being wrong in the internet will be more provocative than asking a question)

For completeness, the definition of monotonicity is that the subset of field elements used by the circuit cannot produce $$0$$ by additions and multiplications. The definition of homogeneity is that all gates of the circuit compute a homogeneus polynomial, i.e., a polynomial whose all monomials have the same degree.

The reason why homogeneity is quite technical restriction is that if $$f$$ is a polynomial that can be computed by an arithmetic circuit of size $$t$$, then the polynomial $$f_d$$ consisting of degree $$d$$ monomials of $$f$$ can be computed by a homogeneous arithmetic circuit of size $$O(d^2 t)$$. (This is for example stated as Lemma 2 in the Hyafil's paper.) This means that we can remove the homogeneity requirement from the theorem if we allow a blow up of a factor $$O(d^3)$$ in the number of terms.

Now, let's see what we need to assume so that the proof works:

First, given a circuit computing a polynomial $$f$$ with degree $$deg(f)$$, we need to find a gate $$v$$ computing a polynomial $$f_v$$ with degree $$deg(f)/3 \le deg(f_v) \le 2deg(f)/3$$. We need to assume fan-in 2 for this, but no other assumptions are required, as for any polynomials $$g,h$$ it holds that $$deg(g) + deg(h) \ge deg(g \diamond h)$$, where $$\diamond$$ is either the sum or the product.

Now that we have found the gate $$v$$, we write the polynomial $$f$$ as $$f = f_v \cdot h + f_{v=0}$$, where $$f_{v=0}$$ is the polynomial obtained from the circuit by setting $$v$$ to zero. No assumptions are required to see that the polynomial $$f_{v=0}$$ can be computed with one gate less than $$f$$, and any assumptions we made about the original circuit that are closed under setting a gate to zero also hold for the circuit computing $$f_{v=0}$$ (in particular, monotonicity or homogeneity). One more important thing is that we have to guarantee that the degree of $$f_{v=0}$$ is at most $$deg(f)$$. This holds if we cannot remove $$v$$ from the circuit without affecting the output and if for all gates in the circuit it holds that $$deg(g \diamond h) \ge \max(deg(g), deg(h))$$, where $$\diamond$$ is the operation computed by the gate and $$g$$ and $$h$$ the inputs. This inequality holds for monotone polynomials and for homogeneous polynomials whenever $$g \diamond h$$ is non-zero, and here we indeed need to assume either monotonicity or homogeneity in order to make the proof work.

What is left is to show that there is such polynomial $$h$$ with $$deg(h) \le 2deg(f)/3$$. The existence of $$h$$ follows by the observation that the polynomial $$f_{v=0}$$ is the same as the polynomial $$f$$, except that some monomials with a factor $$f_v$$ are missing. This can be proved by induction by separating the polynomials computed by each gate to two parts, the part coming from $$v$$ and the other part. The degree of $$h \cdot f_v$$ is at most $$deg(f)$$ because the degrees of $$f_{v=0}$$ and $$f$$ are at most $$deg(f)$$. Now, $$deg(h) \le 2deg(f)/3$$ follows from the facts that $$deg(f_v) \ge deg(f)/3$$ and $$deg(h \cdot f_v) = deg(h) + deg(f_v)$$, which is because the polynomials are over a field, which is a standard assumption in arithmetic circuits .

This would complete the proof of the version of the theorem that I stated in the question, but that version is missing an important property: if we assume either homogeneity or monotonicity, can we assume homogeneity or monotonicity of $$f_v$$ and $$h$$? For monotonicity, we see that the process of separating $$h$$ from $$f$$ by induction is closed under monotone arithmetic. For homogeneity, we have that $$f_v$$ and $$f_{v=0}$$ are homogeneous, so $$h$$ cannot be non-homogeneous because then $$f$$ would be non-homogeneous.

To summarize, the assumptions of this theorem are:

• The polynomials are over a field. This is a standard assumption in arithmetic circuits .
• The gates of the circuit have fan-in 2.
• The circuit is homogeneous or monotone, or we have some other argument to guarantee that $$deg(f + g) = \max(deg(f), deg(g))$$ for $$+$$ gates with inputs $$f$$ and $$g$$.

 Shpilka, Amir, and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Now Publishers Inc, 2010.