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

New for: D1, D2, D3, D4, D5
<< 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:AG1 Advanced Mini-Course
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Monday, 12 January 2015
Duration:60 Minutes
Building:E1 4
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):
  • Karteek Sreenivasaiah, 03/12/2015 01:42 PM -- Created document.