<p>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)</p>
<p>For completeness, the definition of monotonicity is that the subset of field elements used by the circuit cannot produce <span class="math-container">$0$</span> 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.</p>
<p>The reason why homogeneity is quite technical restriction is that if <span class="math-container">$f$</span> is a polynomial that can be computed by an arithmetic circuit of size <span class="math-container">$t$</span>, then the polynomial <span class="math-container">$f_d$</span> consisting of degree <span class="math-container">$d$</span> monomials of <span class="math-container">$f$</span> can be computed by a homogeneous arithmetic circuit of size <span class="math-container">$O(d^2 t)$</span>. (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 <span class="math-container">$O(d^3)$</span> in the number of terms.</p>
<p>Now, let's see what we need to assume so that the proof works:</p>
<p>First, given a circuit computing a polynomial <span class="math-container">$f$</span> with degree <span class="math-container">$deg(f)$</span>, we need to find a gate <span class="math-container">$v$</span> computing a polynomial <span class="math-container">$f_v$</span> with degree <span class="math-container">$deg(f)/3 \le deg(f_v) \le 2deg(f)/3$</span>. We need to assume fan-in 2 for this, but no other assumptions are required, as for any polynomials <span class="math-container">$g,h$</span> it holds that <span class="math-container">$deg(g) + deg(h) \ge deg(g \diamond h)$</span>, where <span class="math-container">$\diamond$</span> is either the sum or the product.</p>
<p>Now that we have found the gate <span class="math-container">$v$</span>, we write the polynomial <span class="math-container">$f$</span> as <span class="math-container">$f = f_v \cdot h + f_{v=0}$</span>, where <span class="math-container">$f_{v=0}$</span> is the polynomial obtained from the circuit by setting <span class="math-container">$v$</span> to zero. No assumptions are required to see that the polynomial <span class="math-container">$f_{v=0}$</span> can be computed with one gate less than <span class="math-container">$f$</span>, and any assumptions we made about the original circuit that are closed under setting a gate to zero also hold for the circuit computing <span class="math-container">$f_{v=0}$</span> (in particular, monotonicity or homogeneity).
One more important thing is that we have to guarantee that the degree of <span class="math-container">$f_{v=0}$</span> is at most <span class="math-container">$deg(f)$</span>.
This holds if we cannot remove <span class="math-container">$v$</span> from the circuit without affecting the output and if for all gates in the circuit it holds that <span class="math-container">$deg(g \diamond h) \ge \max(deg(g), deg(h))$</span>, where <span class="math-container">$\diamond$</span> is the operation computed by the gate and <span class="math-container">$g$</span> and <span class="math-container">$h$</span> the inputs.
This inequality holds for monotone polynomials and for homogeneous polynomials whenever <span class="math-container">$g \diamond h$</span> is non-zero, and here we indeed need to assume either monotonicity or homogeneity in order to make the proof work.</p>
<p>What is left is to show that there is such polynomial <span class="math-container">$h$</span> with <span class="math-container">$deg(h) \le 2deg(f)/3$</span>.
The existence of <span class="math-container">$h$</span> follows by the observation that the polynomial <span class="math-container">$f_{v=0}$</span> is the same as the polynomial <span class="math-container">$f$</span>, except that some monomials with a factor <span class="math-container">$f_v$</span> are missing. This can be proved by induction by separating the polynomials computed by each gate to two parts, the part coming from <span class="math-container">$v$</span> and the other part.
The degree of <span class="math-container">$h \cdot f_v$</span> is at most <span class="math-container">$deg(f)$</span> because the degrees of <span class="math-container">$f_{v=0}$</span> and <span class="math-container">$f$</span> are at most <span class="math-container">$deg(f)$</span>.
Now, <span class="math-container">$deg(h) \le 2deg(f)/3$</span> follows from the facts that <span class="math-container">$deg(f_v) \ge deg(f)/3$</span> and <span class="math-container">$deg(h \cdot f_v) = deg(h) + deg(f_v)$</span>, which is because the polynomials are over a field, which is a standard assumption in arithmetic circuits [1].</p>
<p>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 <span class="math-container">$f_v$</span> and <span class="math-container">$h$</span>? For monotonicity, we see that the process of separating <span class="math-container">$h$</span> from <span class="math-container">$f$</span> by induction is closed under monotone arithmetic. For homogeneity, we have that <span class="math-container">$f_v$</span> and <span class="math-container">$f_{v=0}$</span> are homogeneous, so <span class="math-container">$h$</span> cannot be non-homogeneous because then <span class="math-container">$f$</span> would be non-homogeneous.</p>
<p>To summarize, the assumptions of this theorem are:</p>
<ul>
<li>The polynomials are over a field. This is a standard assumption in arithmetic circuits [1].</li>
<li>The gates of the circuit have fan-in 2.</li>
<li>The circuit is homogeneous <strong>or</strong> monotone, or we have some other argument to guarantee that <span class="math-container">$deg(f + g) = \max(deg(f), deg(g))$</span> for <span class="math-container">$+$</span> gates with inputs <span class="math-container">$f$</span> and <span class="math-container">$g$</span>.</li>
</ul>
<p>[1] Shpilka, Amir, and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Now Publishers Inc, 2010.</p>

CC BY-SA 4.0
2021-01-06T12:21:07.380Z
2021-01-06T12:26:40.517Z
2021-01-06T12:26:40.517Z
Laakeri
<p>I'm new to circuit complexity, and trying to understand Hyafil's decomposition theorem (Theorem 1 in [1], Lemma 3 in [2], Decomposition Lemma in [3], also mentioned in [4]). 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)?</p>
<p>The statement of the theorem is: Let <span class="math-container">$f$</span> be a polynomial of degree <span class="math-container">$deg(f)$</span> computed by an arithmetic circuit** with <span class="math-container">$t$</span> gates. The polynomial <span class="math-container">$f$</span> can be written as <span class="math-container">$f = g_1 \cdot h_1 + \ldots + g_t \cdot h_t$</span>, where <span class="math-container">$deg(g_i) \le 2deg(f)/3$</span> and <span class="math-container">$deg(h_i) \le 2deg(f)/3$</span>.</p>
<p>** with some restrictions</p>
<p>This theorem is proved by repeatedly finding a gate <span class="math-container">$v$</span> that computes a polynomial <span class="math-container">$f_v$</span> where <span class="math-container">$deg(f)/3 \le deg(f_v) \le 2deg(f)/3$</span> and writing the polynomial as <span class="math-container">$f = f_v \cdot h + f_{v=0}$</span>, where <span class="math-container">$h$</span> is some polynomial that must be of degree at most <span class="math-container">$2deg(f)/3$</span> and <span class="math-container">$f_{v=0}$</span> is the polynomial obtained by setting the gate <span class="math-container">$v$</span> to zero.</p>
<p>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 <span class="math-container">$g$</span> and <span class="math-container">$h$</span> it holds that <span class="math-container">$deg(g+h) = \max(deg(g), deg(h))$</span> and <span class="math-container">$deg(g \cdot h) = deg(g) + deg(h)$</span>.) Am I missing something?</p>
<p>[1] Hyafil, L. (1979). On the parallel evaluation of multivariate polynomials. SIAM Journal on Computing, 8(2), 120-123.</p>
<p>[2] 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).</p>
<p>[3] <a href="https://arxiv.org/pdf/1803.05380v1.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1803.05380v1.pdf</a></p>
<p>[4] <a href="https://arxiv.org/pdf/1710.09502.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1710.09502.pdf</a></p>

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

(Asked by: username_0 on 2020-12-23)

I'm new to circuit complexity, and trying to understand Hyafil's decomposition theorem (Theorem 1 in [1], Lemma 3 in [2], Decomposition Lemma in [3], also mentioned in [4]). 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?

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

[2] 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).

[3] <https://arxiv.org/pdf/1803.05380v1.pdf>

[4] <https://arxiv.org/pdf/1710.09502.pdf>

**Tags:** arithmetic-circuits


---

## 1 answers

### Answer by username_0 on 2021-01-06. Score: 1 | Accepted answer

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 [1].

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 [1].
* 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$.

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


---

