Revised: June 8, 2016

Published: September 7, 2016

**Keywords:**complexity theory, lower bounds, algebraic complexity, polynomials, circuits, circuit complexity, arithmetic circuits, noncommutative ring, skew circuits

**Categories:**complexity theory, lower bounds, algebraic complexity, polynomials - multivariate, circuits, circuit complexity, arithmetic circuits, ring, noncommutative, skew circuits

**ACM Classification:**F.1.3

**AMS Classification:**68Q15, 68Q17

**Abstract:**
[Plain Text Version]

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.