Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Lower bounds for non-commutative skew circuits
Speaker:Guillaume Malod
coming from:University Paris Diderot
Speakers Bio:
Event Type:Talk
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 19 March 2015
Duration: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.

Name(s):Karteek Sreenivasaiah
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created by:Karteek Sreenivasaiah, 03/12/2015 01:43 PMLast modified by:Uwe Brahm/MPII/DE, 03/19/2015 04:01 AM
  • Karteek Sreenivasaiah, 03/12/2015 01:48 PM
  • Karteek Sreenivasaiah, 03/12/2015 01:43 PM -- Created document.