ECCC-Report TR23-122https://eccc.weizmann.ac.il/report/2023/122Comments and Revisions published for TR23-122en-usSun, 20 Aug 2023 07:18:09 +0300
Paper TR23-122
| On Lifting Lower Bounds for Noncommutative Circuits using Automata |
Vikraman Arvind,
Abhranil Chatterjee
https://eccc.weizmann.ac.il/report/2023/122We revisit the main result of Carmosino et al \cite{CILM18} which shows that an $\Omega(n^{\omega/2+\epsilon})$ size noncommutative arithmetic circuit size lower bound (where $\omega$ 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. Sun, 20 Aug 2023 07:18:09 +0300https://eccc.weizmann.ac.il/report/2023/122