Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-122 | 9th August 2023 13:22

On Lifting Lower Bounds for Noncommutative Circuits using Automata

RSS-Feed




TR23-122
Authors: Vikraman Arvind, Abhranil Chatterjee
Publication: 20th August 2023 07:18
Downloads: 277
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint