Bera, Suman K. ;
Chakrabarti, Amit
A DepthFive Lower Bound for Iterated Matrix Multiplication
Abstract
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 depthfive Sigma Pi Sigma Pi Sigma arithmetic circuit with the bottom fanin bounded by N^(1/2epsilon). By a depthreduction result of Tavenas, this size lower bound is optimal and can be achieved by the weaker class of homogeneous depthfour 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 depthfour 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 fanin at most N^(1epsilon), for the harder problem of computing certain polynomials defined by NisanWigderson designs.
BibTeX  Entry
@InProceedings{bera_et_al:LIPIcs:2015:5062,
author = {Suman K. Bera and Amit Chakrabarti},
title = {{A DepthFive Lower Bound for Iterated Matrix Multiplication}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {183197},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5062},
URN = {urn:nbn:de:0030drops50622},
doi = {10.4230/LIPIcs.CCC.2015.183},
annote = {Keywords: arithmetic circuits, iterated matrix multiplication, depth five circuits, lower bound}
}
2015
Keywords: 

arithmetic circuits, iterated matrix multiplication, depth five circuits, lower bound 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 