Chicago Journal of Theoretical Computer Science

Volume 2025 Abstracts


  1. On Lifting Lower Bounds for Noncommutative Circuits using Automata by V. Arvind and Abhranil Chatterjee
    April 14, 2025

    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.


[] Volume 2024 Abstracts
[back] Volume 2025 [back] Published articles
[CJCTS home]


Janos Simon