Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Srikanth Srinivasan: Lower bounds for non-commutative skew circuits

LFCS Seminar: Srikanth Srinivasan: Lower bounds for non-commutative skew circuits

— filed under:

What
  • LFCS Seminar
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 non-commutative skew circuits

 

Abstract: We consider lower bounds for non-commutative 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

non-commutative formulas and more generally, for non-commutative

algebraic branching programs due to Nisan (STOC 1991). However,

proving general non-commutative 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 non-commutative 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

non-commutative circuits, we also extend our techniques to prove a

superpolynomial lower bound for any class of circuits that has a

smaller than maximal "non-skew-depth". 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.

Document Actions