{"id":"openai-math/Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication","pdf":"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","url":"https://github.com/openai/math/tree/main/preprints/Homogeneous-depth-five-lower-bounds-for-iterated-matrix-multiplication-September-25-2026","tags":["arithmetic-circuits","algebraic-complexity","matrix-multiplication"],"score":0,"title":"Homogeneous depth-five lower bounds for iterated matrix multiplication","domain":"Theoretical computer science","family":"135","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":false,"family_title":"Homogeneous depth-five lower bounds for iterated matrix multiplication"}