2026-07-21T23:52:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5062 2024-03-06T10:35:46Z ddc:004 open_access

A Depth-Five Lower Bound for Iterated Matrix Multiplication Bera, Suman K. Chakrabarti, Amit arithmetic circuits iterated matrix multiplication depth five circuits lower bound We prove that certain instances of the iterated matrix multiplication (IMM) family of polynomials with N variables and degree n require N^(Omega(sqrt(n))) gates when expressed as a homogeneous depth-five Sigma Pi Sigma Pi Sigma arithmetic circuit with the bottom fan-in bounded by N^(1/2-epsilon). By a depth-reduction result of Tavenas, this size lower bound is optimal and can be achieved by the weaker class of homogeneous depth-four Sigma Pi Sigma Pi circuits. Our result extends a recent result of Kumar and Saraf, who gave the same N^(Omega(sqrt(n))) lower bound for homogeneous depth-four Sigma Pi Sigma Pi circuits computing IMM. It is analogous to a recent result of Kayal and Saha, who gave the same lower bound for homogeneous Sigma Pi Sigma Pi Sigma circuits (over characteristic zero) with bottom fan-in at most N^(1-epsilon), for the harder problem of computing certain polynomials defined by Nisan-Wigderson designs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Suman K. Bera and Amit Chakrabarti 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.183 urn:nbn:de:0030-drops-50622 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.183 eng https://creativecommons.org/licenses/by/3.0/legalcode