A depth-five lower bound for iterated matrix multiplication

DOI10.4230/LIPICS.CCC.2015.183MaRDI QIDQ4601828zbMATH OpenFDO

Authors Suman K. Bera, Amit Chakrabarti

Publication date 24 January 2018

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2015.183

zbMATH Keywords

arithmetic circuitsdepth-five circuitsiterated matrix multiplicationlower bound

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• On the power of homogeneous depth 4 arithmetic circuits

Cited in

(7)

• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
• The computational power of depth five arithmetic circuits
• Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Superpolynomial lower bounds against low-depth algebraic circuits

This page was built for publication: A depth-five lower bound for iterated matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601828)