Family 135Theoretical computer scienceNo LeanNot yet digested

Homogeneous depth-five lower bounds for iterated matrix multiplication

Over every characteristic-zero field, the

(1,1)

entry of a product of n independent

n\times n

variable matrices requires

n^{\Theta(\sqrt n)}

gates in homogeneous depth-five sum–product circuits. This sharp bound allows shared gates and bottom linear forms involving all variables.

Manuscripts in this family · 1

Homogeneous depth-five lower bounds for iterated matrix multiplication

Sep 25, 2026·Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026.pdf

Let

\mathop{\mathrm{IMM}}\nolimits _{n,n}

be the

(1,1)

entry of a product of n independent

n\times n

matrices of variables. Over every field of characteristic zero, every syntactically homogeneous

\Sigma\Pi\Sigma\Pi\Sigma

circuit computing

\mathop{\mathrm{IMM}}\nolimits _{n,n}

has at least

n^{\sqrt n/400}

gates for all sufficiently large n, with an absolute threshold independent of the field. Bottom linear forms may have arbitrary support, and arbitrary finite fan-in, fan-out, and gate sharing are allowed. Over every field, a block expansion gives such circuits with at most

n^{\sqrt n+4}

gates for n ≥ 2. Thus the gate complexity over characteristic-zero fields is

n^{\Theta(\sqrt n)}

Full abstract

PDF on GitHub LaTeX source