Campus Event Calendar

Event Entry

What and Who

Lower bounds for non-commutative skew circuits

Guillaume Malod
University Paris Diderot
AG 1  
AG Audience

Date, Time and Location

Thursday, 19 March 2015
60 Minutes


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. As far as we know, this is the strongest model of non-commutative computation for which we have superpolynomial lower bounds.

Joint work with Nutan Limaye and Srikanth Srinivasan.


Karteek Sreenivasaiah
--email hidden
passcode not visible
logged in users only

Karteek Sreenivasaiah, 03/12/2015 13:48
Karteek Sreenivasaiah, 03/12/2015 13:43 -- Created document.