Name
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 noncommutative 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 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.4086/toc.2016.v012a012 | THEORY OF COMPUTING |
Keywords | DocType | Volume |
complexity theory,lower bounds,algebraic complexity,polynomials,circuits,circuit complexity,arithmetic circuits,noncommutative ring,skew circuits | Journal | 12 |
Issue | ISSN | Citations |
1 | 1557-2862 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nutan Limaye | 1 | 134 | 20.59 |
| Guillaume Malod | 2 | 54 | 4.53 |
| Srikanth Srinivasan | 3 | 132 | 21.31 |