Non-commutative lower bounds

April 3, 2017

Guillaume Lagarde (IRIF)

No knowledge in arithmetic complexity will be assumed.
We still don’t know an explicit polynomial that requires non-commutative circuits of size at least superpolynomial.
However, the context of non commutativity seems to be convenient to get such lower bound because the rigidity of the non-commutativity implies a lot of constraints about the ways to compute.
It is in this context that Nisan, in 1991, provides an exponential lower bound against the non commutative Algebraic Branching Programs computing the permanent, the very first one in arithmetic complexity. We show that this result can be naturally seen as a particular case of a theorem about circuits with *unique parse tree*, and show some extensions to get closer to lower bounds for general NC circuits.
Two joint works: with Guillaume Malod and Sylvain Perifel; with Nutan Limaye and Srikanth Srinivasan.