Lower Bounds for Noncommutative Circuits with Low Syntactic Degree

Let $𝔽$ be a field and $X=\{x_1,\mathrm{\dots },x_n\}$ be a set of variables. A noncommutative polynomial $f(X)$ over $𝔽$ in the variables $X$ is a finite $𝔽$-linear combination of noncommutative monomials in $X$ (equivalently, one may think of these as words in ${\{x_1,\mathrm{\dots },x_n\}}^{\ast }$). The set of all such polynomials forms a ring under addition and noncommutative multiplication, this is the noncommutative polynomial ring denoted by $𝔽⟨X⟩$. In noncommutative arithmetic circuit complexity, the central object of study is the noncommutative arithmetic circuit. A noncommutative arithmetic circuit (we will often simply say circuit for short), is a directed acyclic graph whose leaves are labeled by variables (say from $X$) and constants from $𝔽$, and whose internal nodes, called gates, are labeled by either $+$ or $\times$. A circuit is said to have fan-in $2$ if each gate has in-degree $2$. Each gate in the circuit computes a polynomial in the natural way: a $+$ gate computes the sum of the polynomials computed at the children and a $\times$ gate computes the product. Importantly, since the product is noncommutative, each product gate comes with an ordering on the children. Since we will deal with fan-in $2$ circuits, each such gate has a designated left child and a designated right child. We will say that a circuit has size $s$ if the underlying graph has $s$ vertices. We will say that a gate $g$ in a circuit has depth $\mathrm{\Delta }$ if the longest leaf to $g$ path in the circuit has length $\mathrm{\Delta }$. The depth of a circuit is then defined as the maximum depth of any gate in it. We designate a particular gate of the circuit to be the output gate, and the polynomial computed by the circuit is defined to be the polynomial computed at this distinguished gate.

A central goal in this area is to prove exponential lower bounds on the size of circuits computing explicit¹¹1We will say that a polynomial $f\in 𝔽⟨X⟩$ is explicit if there is a polynomial time algorithm that computes, given a monomial $m\in X^{\ast }$, the coefficient of $m$ in $f$. polynomials. The most influential work in this area is that of Nisan [6]. He showed exponential lower bounds on the size of formulas computing explicit polynomials. Formulas are circuits whose underlying graph is a tree. In order to show this, he introduced a complexity measure, now called Nisan Rank. Unfortunately, his methods do not provide such strong bounds for circuits. Indeed, the best lower bounds on the circuit size of an explicit, $n$ variate degree $\mathrm{\Theta }(n)$ polynomial are of the form $\mathrm{\Omega }(n\log n)$ [7, 1] and improving upon this has been an outstanding open problem for more than $40$ years. The work of Carmosino et al. [3] provides strong motivation to improve upon the $n\log n$ bound: they show, for instance, that barely superlinear lower bounds (of the form $\mathrm{\Omega }(n^{\omega /2+ϵ})$, where $\omega$ is the exponent of matrix multiplication) for noncommutative circuits computing constant degree polynomials can be amplified to obtain exponential lower bounds.

In a recent work [4], Chatterjee and Hrubeš improve upon the $\mathrm{\Omega }(n\log n)$ bound, assuming that the circuit is homogeneous. A circuit is said to be homogeneous if every gate in it computes a homogeneous polynomial. In their main result ([4], Theorem 14), they construct an $n$ variate, degree $\mathrm{\Theta }(n)$ polynomial $f$ such that any homogeneous circuit computing $f$ requires size $\mathrm{\Omega }(n^2)$.

Note that noncommutative circuits can be homogenized, but this procedure incurs a multiplicative blowup of $d^2$ (where $d$ is the degree of the polynomial) in size and therefore the results in the paper discussed above fall short of giving lower bounds for general (not necessarily homogeneous) circuits.

The work of Chatterjee and Hrubeš [4] leaves open (and tantalizingly so) the question of going beyond homogeneous circuits and proving $\omega (n\log n)$ lower bounds for general circuits. In this work, we take a step in this direction. We remove the homogeneity restriction and replace it with a bound on the syntactic degree. Let $\mathrm{\Psi }$ be a circuit. For each gate $g$ in $\mathrm{\Psi }$, we define the syntactic degree $d(g)$ inductively as follows: for a leaf $g$ labeled by a field constant, we define $d(g)=0$. For a leaf labeled by a variable, we define $d(g)=1$. For a sum gate $g=g_1+g_2$ we define $d(g)=\max \{d(g_1),d(g_2)\}$. If $g=g_1\times g_2$ is a product gate, we define $d(g)=d(g_1)+d(g_2)$. Note that for each gate $g$, the degree of the polynomial computed at $g$ is at most $d(g)$. The syntactic degree of $\mathrm{\Psi }$ is then defined as the maximum over all gates $g$ of $\mathrm{\Psi }$ of $d(g)$.

Notice that if we have a homogeneous circuit $\mathrm{\Psi }$ for a degree $d$ polynomial, we can assume without loss of generality that the syntactic degree of $\mathrm{\Psi }$ is exactly $d$. This is because in such a circuit, each gate $g$ either computes a polynomial of degree equal to $d(g)$, or it computes the $0$ polynomial. This is well known [5] and easily proved, for example by induction. Therefore, homogeneity forbids (useful) computation of polynomials of degree larger than $d$. This simple observation suggests a natural relaxation of homogeneity: allowing the circuit to have syntactic degree larger than the degree of the output, but not much more. Such relaxations of homogeneity have been examined in the literature. For instance, in a recent result, the authors of [5] provided a quasi-homogenization result for commutative formulas. A formula is said to be quasi-homogeneous if the syntactic degree of the formula is a polynomially bounded (from above) by the degree of the output.

Quantitatively, we recall that Chatterjee and Hrubeš have proved an $\mathrm{\Omega }(n^2)$ lower bound on the size of any homogeneous noncommutative circuit computing some explicit polynomial on $n$ variables of degree $\mathrm{\Theta }(n)$. In contrast, for general circuits, the strongest known lower bound remains $\mathrm{\Omega }(n\log n)$.

One can now ask the following intermediate question: can we prove better-than-$\mathrm{\Omega }(n\log n)$ lower bounds on the size of circuits computing an explicit $n$ variate, degree $\mathrm{\Theta }(n)$ polynomial where the circuit is not necessarily homogeneous, but has syntactic degree, say, $O(n)$? Such circuits may compute intermediate inhomogeneous polynomials of degree higher than the degree of the output, but not much higher. We answer this question in the affirmative.

Let $X=\{x_1,\mathrm{\dots },x_n\}$ and $Y=\{y_1,\mathrm{\dots },y_n\}$. Our results apply to the palindrome polynomial ${\mathrm{Pal}}_{n,n}(X,Y)\in 𝔽⟨X,Y⟩$ where ${\mathrm{Pal}}_{n,d}(X,Y)\in 𝔽⟨X,Y⟩$ is defined as follows:

A version of this polynomial was already introduced by Nisan in [6] to separate circuits from formulas. Indeed, there exists a homogeneous circuit of size $O(n^2)$ that computes ${\mathrm{Pal}}_{n,n}(X,Y)$. We obtain this from the recursive expression ${\mathrm{Pal}}_{n,d}={\sum }_{i=1}^n{x}_i{\mathrm{Pal}}_{n,d-1}{y}_i$. On the other hand, it follows from Nisan’s work [6] that any formula computing ${\mathrm{Pal}}_{n,n}(X,Y)$ requires size $n^{\mathrm{\Omega }(n)}$. Since a fan-in two circuit with depth $\mathrm{\Delta }$ can be converted into a formula of size $\le 2^{\mathrm{\Delta }}$, it follows that any circuit computing ${\mathrm{Pal}}_{n,n}(X,Y)$ must have depth, and therefore size, $\mathrm{\Omega }(n\log n)$. In this paper we improve upon this lower bound for circuits with low syntactic degree. As alluded to before, our main results are the following.

Theorem 2 offers a qualitative strengthening of the main theorem in the work of Chatterjee and Hrubeš ([4], Theorem 14), since their result applies to homogeneous circuits while ours applies to a provably stronger class of circuits (Remark 1).

Next, we analyze the circuit size required to compute ${\mathrm{Pal}}_{n,n}$ based on the number of different syntactic degrees that appear in the circuit. We show that for a circuit if this number is $o(n\log n)$, then it must have size $\omega (n\log n)$.

Note that Theorem 3 applies to circuits with arbitrarily high syntactic degree. We only require that the number of distinct $d(g)$’s appearing in $\mathrm{\Psi }$ satisfies the constraints mentioned above. Also, note that if $d^{\prime }=\omega (n\log n)$, we trivially get an $\omega (n\log n)$ bound: if a circuit has $\omega (n\log n)$ types of gates then it must have $\omega (n\log n)$ gates. So, the only case where we do not obtain a lower bound asymptotically better than $\mathrm{\Omega }(n\log n)$ is when $d^{\prime }$ and the size of $\mathrm{\Psi }$ are both $\mathrm{\Theta }(n\log n)$. We do not know if such circuits exist for ${\mathrm{Pal}}_{n,n}$.

Theorem 3 has the following immediate corollary:

Finally, in Section 5 we analyze a construction provided in the work of Chatterjee and Hrubeš, and show a fine grained separation between homogeneous circuits and circuits with low syntactic degree.

We use the methods of Nisan [6] to obtain our lower bounds. Specifically, we bound the dimension of the coefficient space of an $X,Y$ separated polynomial computed by a circuit of low syntactic degree: Let $f\in 𝔽⟨X,Y⟩$ be a polynomial. We say $f$ is $X,Y$ separated if in each nonzero monomial of $f$, every $X$ variable appears before every $Y$ variable. Note that the ${\mathrm{Pal}}_{n,d}(X,Y)$ polynomials are $X,Y$ separated. Now suppose $f$ is $X,Y$ separated. Thinking of $f$ as a polynomial in the $Y$ variables with coefficients that are elements of $𝔽⟨X⟩$, we write

where $c_m\in 𝔽⟨X⟩$. Define ${\mathrm{𝖼𝗈𝖾𝖿𝖿}}_{𝗆}(f)\triangleq c_m$, and ${\mathrm{𝖢𝗈𝖾𝖿𝖿}}_X(f)\triangleq \{{\mathrm{𝖼𝗈𝖾𝖿𝖿}}_{𝗆}(f)\mid m\in Y^{\ast }\}$. Recalling that the ring $𝔽⟨X⟩$ forms an $𝔽$-vector space with $X^{\ast }$ as a basis, we consider the dimension of the $𝔽$-span of the set ${\mathrm{𝖢𝗈𝖾𝖿𝖿}}_X(f)$. For $f={\mathrm{Pal}}_{n,n}(X,Y)$, this quantity is $n^n$. On the other hand, Nisan, in [6], showed that if $f$ is computed by a formula of size $s$, then this dimension is bounded above by $s^{O(1)}$. Since a circuit of size $s$ can be converted into a formula of size $\le 2^s$, his method applied directly gives a lower bound of $\mathrm{\Omega }(n\log n)$ on the size of any circuit computing ${\mathrm{Pal}}_{n,n}(X,Y)$. We refine this analysis and show that if an $X,Y$ separated polynomial is computed by a circuit with restrictions on the syntactic degrees appearing in it, we may obtain a better upper bound on the dimension of the span of the coefficients, by explicitly constructing a spanning set of polynomials. This gives the lower bounds. For future convenience, we set up some more notation. Let $\mathrm{\Psi }$ be a noncommutative circuit. Recall that for a gate $g$ in $\mathrm{\Psi }$, $d(g)$ denotes its syntactic degree. Define $D_{\mathrm{\Psi }}\triangleq \{d(g)\mid g\text{ is a gate in }\mathrm{\Psi }\}$. We say that a circuit $\mathrm{\Psi }$ is in normal form if no product gate has a child of syntactic degree $0$. Since gates with syntactic degree $0$ can only compute constants, we may assume without loss of generality, by pushing constants all the way down to the leaves, that a given circuit is in normal form. We allow leaves labeled by $\alpha x$ where $\alpha \in 𝔽$ and $x$ is a variable. Such leaves also have syntactic degree $1$.

In this section, we prove our main result. Theorems 2, 4 and 3 follow as corollaries of Theorem 6, which we prove below.

In this section, we observe that low syntactic degree circuits are provably more powerful than homogeneous circuits in a fine grained sense. We will consider the ordered symmetric polynomials ${\mathrm{OS}}_n^k$ defined as follows:

On the one hand, Chatterjee and Hrubeš showed ([4], Theorem 14) the following lower bound:

On the other hand, they observe ([4], Section 5) that a well known construction ([2], Chapters 2.1-2.3) of circuits of size $O(n{\log }^{2}n)$ computing the commutative elementary symmetric polynomials (this construction uses the Fast Fourier Transform) continues to hold noncommutatively. Here, we observe that the syntactic degree of this (noncommutative) circuit, which simultaneously computes ${\{{\mathrm{OS}}_n^k\}}_{k=0}^n$, is $n$.

For completeness, we present the construction here and analyze the syntactic degree of the resulting circuit. For simplicity, we work over the complex numbers, and we assume that $n$ is a power of $2$. The circuit $C_n$ is constructed such that it simultaneously computes the set ${\{{\mathrm{OS}}_n^k\}}_{k=0}^n$ of polynomials. $C_n$ will have size $O(n{\log }^{2}n)$ and syntactic degree $n$.

The basic observation is that for each $k$, ${\mathrm{OS}}_n^k$ is the coefficient of $t^{n-k}$ in ${\prod }_{i=1}^n(x_i+t)$. Here $t$ commutes with the $x_i$’s.

By induction, we assume that we have circuits $C_{n/2}^1$ and $C_{n/2}^2$ that compute the coefficients of $1,t,\mathrm{\dots },t^{n/2}$ in the polynomials $A(t)={\prod }_{i=1}^{n/2}(x_i+t)$ and $B(t)={\prod }_{i=n/2+1}^n(x_i+t)$ respectively. We are now interested in computing the coefficients of $1,t,\mathrm{\dots },t^n$ in the polynomial $A(t)B(t)$. In order to do this, we implement the well known FFT based algorithm for univariate polynomial multiplication. Let $\omega \in ℂ$ be a primitive $2n$-th root of unity.

• $\mathrm{■}$

  Evaluation: Using the Fast Fourier Transform (FFT) and the circuits $C_{n/2}^1$ and $C_{n/2}^2$ which represent coefficient vectors of $A(t)$ and $B(t)$ respectively, we construct two circuits ${\mathrm{\Phi }}_1$ and ${\mathrm{\Phi }}_2$ for computing $A(1),A(\omega ),\mathrm{\dots },A({\omega }^{2n-1})$ and $B(1),B(\omega ),\mathrm{\dots },B({\omega }^{2n-1})$ respectively. Importantly, the syntactic degree of ${\mathrm{\Phi }}_1$ and ${\mathrm{\Phi }}_2$ is exactly the same as that of $C_{n/2}^1$ and $C_{n/2}^2$, which by induction is $n/2$. This is because the FFT implements a linear transformation which never multiplies the entries of the coefficient vectors.

• $\mathrm{■}$

  Pointwise Product: Next, we use ${\mathrm{\Phi }}_1$ and ${\mathrm{\Phi }}_2$ to construct a circuit $\mathrm{\Phi }$ which simultaneously computes the polynomials $A(1)B(1),A(\omega )B(\omega ),\mathrm{\dots },$ $A({\omega }^{2n-1})B({\omega }^{2n-1})$. The syntactic degree of $\mathrm{\Phi }$ is $n$.

• $\mathrm{■}$

  Interpolation: Finally, we again use the (inverse) FFT to construct the circuit $C_n$ which computes the coefficients ${\{{\mathrm{OS}}_n^k\}}_{k=0}^n$ of the power of $t$ in $A(t)B(t)$. This step does not increase the syntactic degree because it’s linear. Therefore, the syntactic degree of $C_n$ is $n$.

$C_n$ in particular computes the polynomial ${\mathrm{OS}}_n^{n/2}$, has size $O(n{\log }^{2}n)$ ([4], [2]) and syntactic degree $n$. It heavily uses inhomogeneity but has low (in terms of $n/2$) syntactic degree. This construction therefore demonstrates the power of low syntactic degree circuits vis-à-vis homogeneous circuits.

In this paper, we proved $\omega (n\log n)$ lower bounds for noncommutative circuits of low syntactic degree. The question of proving such lower bounds for general circuits remains open. One possible avenue of attack for this problem is inventing a size preserving procedure for reducing a circuit’s syntactic degree. As a concrete question, suppose we are given a circuit of size $s$ and syntactic degree $d=\omega (n)$ that computes ${\mathrm{Pal}}_{n,n}$. Can we construct another circuit computing ${\mathrm{Pal}}_{n,n}$ with syntactic degree $O(n)$ and size $s\times n^{o(1)}$? An affirmative answer to this question, combined with our work, would immediately yield strong lower bounds for general circuits. Reducing syntactic degree is no harder (and perhaps easier) than homogenization, so one may expect a more efficient way to do it than simple homogenization. Another question that stems from this work is whether we can handle separately the case when the number of distinct syntactic degrees appearing in a circuit computing ${\mathrm{Pal}}_{n,n}$ is $\mathrm{\Theta }(n\log n)$.