Homogeneous depth-five lower bounds for iterated matrix multiplication
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)}\).
Cite
@misc{OAI:Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026,
author = {{OpenAI}},
title = {{Homogeneous depth-five lower bounds for iterated matrix multiplication}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026/Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026.pdf}{OAI:Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026}},
year = {2026}
}