@article{doi:10.1137/140990280,
    Abstract = {We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth-4 arithmetic formula computing the product of \$d\$ generic matrices of size \$n \times n\$, \$\mathrm{IMM}\\_{n,d}\$, has size \$n^{\Omega(\sqrt{d})}\$ as long as \$d = n^{O(1)}\$. This improves the result of Nisan and Wigderson [Comput. Complexity, 6 (1997), pp. 217--234] for depth-4 set-multilinear formulas. We also study \$\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}\$ formulas, which are depth-4 formulas with the stated bounds on the fan-ins of the \$\Pi\$ gates. A recent depth reduction result of Tavenas [Lecture Notes in Comput. Sci. 8087, 2013, pp. 813--824] shows that any \$n\$-variate degree \$d = n^{O(1)}\$ polynomial computable by a circuit of size \$\mathop{\mathrm{poly}}(n)\$ can also be computed by a depth-4 \$\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}\$ formula of top fan-in \$n^{O(d/t)}\$. We show that any such formula computing \$\mathrm{IMM}\\_{n,d}\$ has top fan-in \$n^{\Omega({d/t})}\$, proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi [Proceedings of STOC, 2014, pp. 146--153], which gives a similar lower bound for an explicit polynomial in VNP.},
    Author = {Fournier, Herv\'{e} and Limaye, Nutan and Malod, Guillaume and Srinivasan, Srikanth},
    EPrint = {https://doi.org/10.1137/140990280},
    File = {Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication - imm-merged.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {5},
    Pages = {1173-1201},
    Title = {Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication},
    URL = {https://doi.org/10.1137/140990280},
    Volume = {44},
    Year = {2015},
    bdsk-url-1 = {https://doi.org/10.1137/140990280},
    date-added = {2023-10-06 11:49:28 +0200},
    date-modified = {2023-10-06 11:49:28 +0200},
    file-2 = {Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication - fournier-et-al-2015-lower-bounds-for-depth-4-formulas-computing-iterated-matrix-multiplication.pdf},
    doi = {10.1137/140990280}
}

@article{doi:10.1137/140990280, Abstract = {We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth-4 arithmetic formula computing the product of \$d\$ generic matrices of size \$n \times n\$, \$\mathrm{IMM}\{n,d}\$, has size \$n^{\Omega(\sqrt{d})}\$ as long as \$d = n^{O(1)}\$. This improves the result of Nisan and Wigderson [Comput. Complexity, 6 (1997), pp. 217--234] for depth-4 set-multilinear formulas. We also study \$\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}\$ formulas, which are depth-4 formulas with the stated bounds on the fan-ins of the \$\Pi\$ gates. A recent depth reduction result of Tavenas [Lecture Notes in Comput. Sci. 8087, 2013, pp. 813--824] shows that any \$n\$-variate degree \$d = n^{O(1)}\$ polynomial computable by a circuit of size \$\mathop{\mathrm{poly}}(n)\$ can also be computed by a depth-4 \$\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}\$ formula of top fan-in \$n^{O(d/t)}\$. We show that any such formula computing \$\mathrm{IMM}\, Author = {Fournier, Herv\'{e} and Limaye, Nutan and Malod, Guillaume and Srinivasan, Srikanth}, EPrint = {https://doi.org/10.1137/140990280}, File = {Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication - imm-merged.pdf}, Journal = {SIAM Journal on Computing}, Number = {5}, Pages = {1173-1201}, Title = {Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication}, URL = {https://doi.org/10.1137/140990280}, Volume = {44}, Year = {2015}, bdsk-url-1 = {https://doi.org/10.1137/140990280}, date-added = {2023-10-06 11:49:28 +0200}, date-modified = {2023-10-06 11:49:28 +0200}, file-2 = {Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication - fournier-et-al-2015-lower-bounds-for-depth-4-formulas-computing-iterated-matrix-multiplication.pdf}, doi = {10.1137/140990280} }}\$ has top fan-in \$n^{\Omega({d/t})}\$, proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi [Proceedings of STOC, 2014, pp. 146--153], which gives a similar lower bound for an explicit polynomial in VNP.