V. Arvind

On Lifting Lower Bounds for Noncommutative Circuits using Automata

2023 · arXiv (Cornell University)

We revisit the main result of Carmosino et al \cite{CILM18} which shows that an $Ω(n^{ω/2+ε})$ size noncommutative arithmetic circuit size lower bound (where $ω$ is the matrix multiplication exponent) for a constant-degree $n$-variate polynomial family …