Theory of Computing
-------------------
Title     : Lower Bounds for Non-Commutative Skew Circuits
Authors   : Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan
Volume    : 12
Number    : 12
Pages     : 1-38
URL       : https://theoryofcomputing.org/articles/v012a012

Abstract
--------

Nisan (STOC 1991) exhibited a polynomial which is computable by
linear-size non-commutative circuits but requires exponential-size
non-commutative algebraic branching programs. Nisan's hard
polynomial is in fact computable by linear-size "skew circuits." 
_Skew circuits_ are circuits where every multiplication gate has the
property that all but one of its children is an input variable or a
scalar. Such multiplication gates are called _skew_ gates.

We prove that any non-commutative skew circuit which computes the
square of the polynomial defined by Nisan must have exponential size.
A simple extension of this result then yields an exponential lower
bound on the size of non-commutative circuits where each
multiplication gate has an argument of degree at most one-fifth of the
total degree.

We also extend our techniques to prove an exponential lower bound for
a class of circuits which is a restriction of general non-commutative
circuits and a generalization of non-commutative skew circuits. We
define the _non-skew depth_ of a circuit to be the maximum number of
non-skew gates on any path from an input gate to the output gate. We
prove lower bounds for non-commutative circuits of small non-skew
depth.

More precisely, we show that for any $k < d$, there is an explicit
polynomial of degree $d$ over $n$ variables that has non-commutative
circuits of polynomial size but such that any circuit with non-skew
depth $k$ must have size at least $n^{\Omega(d/k)}$. It is not hard to
see that any polynomial of degree $d$ that has polynomial-size
circuits has a polynomial-size circuit with non-skew depth $d$. Hence,
our results should be interpreted as proving lower bounds for the
class of circuits with non-trivially small non-skew depth.

As far as we know, this is the strongest model of non-commutative
computation for which we have superpolynomial lower bounds.