theoretical-computer-science / Algebraic complexity; arithmetic circuit lower bounds

Homogeneous depth-five lower bounds for iterated matrix multiplication with unrestricted bottom fan-in (Bera-Chakrabarti question, balanced regime)

Claims that over every field of characteristic zero every syntactically homogeneous ΣΠΣΠΣ\Sigma\Pi\Sigma\Pi\Sigma circuit computing IMMn,n\mathrm{IMM}_{n,n} has at least nn/400n^{\sqrt n/400} gates for large nn, with gate sharing, arbitrary fan-in and bottom linear forms of arbitrary support allowed, and a block construction gives nn+4n^{\sqrt n+4} over every field, so the gate complexity is nΘ(n)n^{\Theta(\sqrt n)}. The measure is the rank of a partial-derivative-times-multiplication operator. It does NOT treat the Bera-Chakrabarti regime IMMnq,n\mathrm{IMM}_{n^q,n} directly, positive characteristic, non-homogeneous circuits, or depths beyond five.

15Significance / 100
1Frontier events
0Verification tasks
0Recorded attempts

Temporal state

Current frontier

No reconciled state yet.

Append-only history

Frontier timeline

theoretical-computer-scienceSep 25, 2026Significance 15/100Registry: lean checked

Homogeneous depth-five lower bounds for iterated matrix multiplication with unrestricted bottom fan-in (Bera-Chakrabarti question, balanced regime)

Prior state unknown→proved

Claims that over every field of characteristic zero every syntactically homogeneous ΣΠΣΠΣ\Sigma\Pi\Sigma\Pi\Sigma circuit computing IMMn,n\mathrm{IMM}_{n,n} has at least nn/400n^{\sqrt n/400} gates for large nn, with gate sharing, arbitrary fan-in and bottom linear forms of arbitrary support allowed, and a block construction gives nn+4n^{\sqrt n+4} over every field, so the gate complexity is nΘ(n)n^{\Theta(\sqrt n)}. The measure i…

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Research memory

Claims and attempts

Scoped claims

Source authenticated

Claims that over every field of characteristic zero every syntactically homogeneous ΣΠΣΠΣ\Sigma\Pi\Sigma\Pi\Sigma circuit computing IMMn,n\mathrm{IMM}_{n,n} has at least nn/400n^{\sqrt n/400} gates for large nn, with gate sharing, arbitrary fan-in and bottom linear forms of arbitrary support allowed, and a block construction gives nn+4n^{\sqrt n+4} over every field, so the gate complexity is nΘ(n)n^{\Theta(\sqrt n)}. The measure is the rank of a partial-derivative-times-multiplication operator. It does NOT treat the Bera-Chakrabarti regime IMMnq,n\mathrm{IMM}_{n^q,n} directly, positive characteristic, non-homogeneous circuits, or depths beyond five.

Claims that over every field of characteristic zero every syntactically homogeneous ΣΠΣΠΣ\Sigma\Pi\Sigma\Pi\Sigma circuit computing IMMn,n\mathrm{IMM}_{n,n} has at least nn/400n^{\sqrt n/400} gates for large nn, with gate sharing, arbitrary fan-in and bottom linear forms of arbitrary support allowed, and a block construction gives nn+4n^{\sqrt n+4} over every field, so the gate complexity is nΘ(n)n^{\Theta(\sqrt n)}. The measure is the rank of a partial-derivative-times-multiplication operator. It does NOT treat the Bera-Chakrabarti regime IMMnq,n\mathrm{IMM}_{n^q,n} directly, positive characteristic, non-homogeneous circuits, or depths beyond five.

Recorded attempts

Evidence graph

Connected research record