ECCC - Reports tagged with factor-closure
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FACTOR-CLOSURE:
Reports tagged with factor-closure:
TR26-300 | 2nd November 2026
Vikraman Arvind, Pushkar Joglekar

Factor Closure in Noncommutative Algebraic Complexity

We prove that $\VPnc$ is closed under taking factors over every field. If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. A central factor $g$ in a decomposition $f=agb$, with nonconstant ... more >>>




ISSN 1433-8092 | Imprint