3
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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