Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-022 | 8th June 2016 12:55

Lower bounds for non-commutative skew circuits

RSS-Feed




Revision #1
Authors: Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
Accepted on: 8th June 2016 12:55
Downloads: 150
Keywords: 


Abstract:

Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized 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). We prove that any non-commutative skew circuit which computes the square of the polynomial defined by Nisan must have exponential size.

As a further step towards proving exponential lower bounds for general non-commutative circuits, 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. More precisely, we consider non-commutative circuits of small non-skew depth, which denotes the maximum number of non-skew gates on any path from the output gate to an input gate. 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-sized 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.



Changes to previous version:

Some proofs were re-written to be clearer and an extension to a larger class of circuits was added.


Paper:

TR15-022 | 9th February 2015 18:24

Lower bounds for non-commutative skew circuits





TR15-022
Authors: Nutan Limaye, Guillaume Malod, Srikanth Srinivasan
Publication: 9th February 2015 19:46
Downloads: 778
Keywords: 


Abstract:

Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized 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). We prove that any non-commutative skew circuit which computes the square of the polynomial defined by Nisan must have exponential size.

As a further step towards proving exponential lower bounds for general non-commutative circuits, 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. More precisely, we consider non-commutative circuits of small non-skew depth, which denotes the maximum number of non-skew gates on any path from the output gate to an input gate. 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-sized 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.



ISSN 1433-8092 | Imprint