Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bera, Suman K.; Chakrabarti, Amit http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-50622
URL:

;

A Depth-Five Lower Bound for Iterated Matrix Multiplication

pdf-format:


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 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.

BibTeX - Entry

@InProceedings{bera_et_al:LIPIcs:2015:5062,
  author =	{Suman K. Bera and Amit Chakrabarti},
  title =	{{A Depth-Five Lower Bound for Iterated Matrix Multiplication}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{183--197},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{David Zuckerman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5062},
  URN =		{urn:nbn:de:0030-drops-50622},
  doi =		{10.4230/LIPIcs.CCC.2015.183},
  annote =	{Keywords: arithmetic circuits, iterated matrix multiplication, depth five circuits, lower bound}
}

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


DROPS-Home | Fulltext Search | Imprint Published by LZI