On Lifting Lower Bounds for Noncommutative Circuits using Automata

08/09/2023

∙

by   V. Arvind, et al.

∙

0

∙

share

We revisit the main result of Carmosino et al <cit.> 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 (g_n)_n, where each g_n is a noncommutative polynomial, can be “lifted” to an exponential size circuit size lower bound for another polynomial family (f_n) obtained from (g_n) by a lifting process. In this paper, we present a simpler and more conceptual automata-theoretic proof of their result.