On Lifting Lower Bounds for Noncommutative Circuits using Automata

2023/08/09 by Arvind, V., Chatterjee, Abhranil
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2308.04854

Abstract

We revisit the main result of Carmosino et al \citeCILM18 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.

Related

• Arithmetic Circuit Lower Bounds via MaxRank
• New Lower Bounds against Homogeneous Non-Commutative Circuits
• Functional lower bounds for restricted arithmetic circuits of depth four
• Observations on Symmetric Circuits
• Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits