Lower Bounds Against Non-Commutative Models of Algebraic Computation
0Prerona Chatterjee (Tel Aviv University)
https://simons.berkeley.edu/talks/prerona-chatterjee-tel-aviv-university-2023-03-22-0
Proof Complexity and Meta-Mathematics
Algebraic circuits 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. In this talk, we will further assume that the multiplication gate is "non-commutative", and the question of interest will be to prove lower bounds against this model for some "explicit" polynomial. Although a lot of progress has been made towards this question in restricted settings, the best lower bound against general non-commutative circuits remains $\Omega(n \log n)$ due to Baur and Strassen.
In this talk, we will then see some new lower bounds against non-commutative circuits under the additional assumption of "homogenity". In particular, we will prove 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)$, thus improving upon the lower bound due to Baur and Strassen.
The talk is based on joint work with Pavel Hrube\v{s} (https://arxiv.org/abs/2301.01676).