Published by the Department of Computer Science, The University of Chicago.

Abstract

We revisit the main result of Carmosino et al [CILM18] which shows that an $\Omega(n^{\omega/2+\gamma})$ 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.

• The article: PDF (247 KB)
• Source material: ZIP (242 KB)
• BibTeX entry for this article (298 bytes)

Submitted December 3, 2023, revised February 15, 2025, published April 14, 2025.

© 2025 V. Arvind and Abhranil Chatterjee
Licensed under a Creative Commons Attribution License

Volume 2024, Article 2

Volume 2025

Published articles