LFCS Seminar: Srikanth Srinivasan: Lower bounds for noncommutative skew circuits
What 


When 
Apr 07, 2015 from 04:00 PM to 05:00 PM 
Where  4.31/4.33 
Add event to calendar 
vCal iCal 
Title: Lower bounds for noncommutative skew circuits
Abstract: We consider lower bounds for noncommutative arithmetic
circuits, i.e. arithmetic circuits that compute polynomials in the
restrictive model where variables do not commute. Contrary to the more
popular commutative setting, we have strong explicit lower bounds for
noncommutative formulas and more generally, for noncommutative
algebraic branching programs due to Nisan (STOC 1991). However,
proving general noncommutative circuit lower bounds remains open.
It has been observed that 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) and hence, proving
lower bounds for such circuits is a natural question to now consider.
We resolve this question by showing that any noncommutative skew
circuit which computes the square of the polynomial defined by Nisan
must have exponential size.
As a further step towards proving lower bounds for general
noncommutative circuits, we also extend our techniques to prove a
superpolynomial lower bound for any class of circuits that has a
smaller than maximal "nonskewdepth". As far as we know, this is the
strongest model of computation for which we have superpolynomial lower
bounds.
Joint work with Nutan Limaye and Guillaume Malod.