Abstract
Algebraic circuits are the most well studied models of algebraic computation. They are directed acyclic graphs where the leaves are labelled by variables or field constants, and internal nodes are labelled by addition (+) or multiplication (x). Therefore, each gate in the circuit naturally computes polynomials over the base field. When the underlying graph is allowed to be a tree, the model of computation becomes an algebraic formula. Another standard model of computation are algebraic branching programs, and their power lies in between that of formulas and circuits. The central question in algebraic circuit complexity is to prove super-polynomial lower bounds against these models for "explicit" polynomials. Studying the relative powers of these models are also important questions. In this talk, we will look at the progress made towards these questions in the restricted setting of "non-commutativity". In this setting, we assume that the multiplication gates in the models are non-commutative or in other words, respect the order of multiplication.
In a seminal work, Nisan showed an exponential separation between the powers of ABPs and circuits in the non-commutative setting. In this talk, we will therefore focus on the progress made since then on the following two questions:
1. Is there an explicit polynomial for which we can prove super-polynomial lower bounds against non-commutative circuits?
2. Is there a polynomial that is computable by a non-commutative ABP for which we can prove super-polynomial lower bounds against non-commutative formulas?
In particular I will speak about a new work with Pavel Hrubes\v{s} where we show an improved lower bound against non-commutative circuits under the additional assumption of "homogenity". We show that any homogeneous non-commutative circuit computing the ordered version of the elementary symmetric polynomial over $n$ variables of degree $n/2$ must have size $\Omega(n^2)$, improving upon the lower bound of $\Omega(n log n)$ due to Baur and Strassen.