License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.38
URN: urn:nbn:de:0030-drops-68730
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6873/
Go to the corresponding LIPIcs Volume Portal

Kumar, Mrinal ; Saptharishi, Ramprasad

Finer Separations Between Shallow Arithmetic Circuits

pdf-format:
LIPIcs-FSTTCS-2016-38.pdf (0.5 MB)

Abstract

In this paper, we show that there is a family of polynomials P_n, where P_n is a polynomial in n variables of degree at most d = O(log^2(n)), such that

* P_n can be computed by linear sized homogeneous depth-5 arithmetic circuits,
* P_n can be computed by poly(n) sized non-homogeneous depth-3 arithmetic circuits.
* Any homogeneous depth-4 arithmetic circuit computing P_n must have size at least n^{Omega(sqrt(d))}.

This shows that the parameters for the depth reduction results of [Agrawal-Vinay 08, Koiran 12, Tavenas 13] are tight for extremely restricted classes of arithmetic circuits, for instance homogeneous depth-5 circuits and non-homogeneous depth-3 circuits, and over an appropriate range of parameters, qualitatively improve a result of [Kumar-Saraf 14], which showed that the parameters of depth reductions are optimal for algebraic branching programs.

As an added advantage, our proofs are much shorter and simpler than the two known proofs of n^{Omega(sqrt(d))} lower bound for homogeneous depth-4 circuits [Kayal-Limaye-Saha-Srinivasan 14, Kumar-Saraf 14], albeit our proofs only work when d = O(log^2(n)).

BibTeX - Entry

@InProceedings{kumar_et_al:LIPIcs:2016:6873,
  author =	{Mrinal Kumar and Ramprasad Saptharishi},
  title =	{{Finer Separations Between Shallow Arithmetic Circuits}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{38:1--38:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6873},
  URN =		{urn:nbn:de:0030-drops-68730},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.38},
  annote =	{Keywords: arithmetic circuits, lower bounds, separations, depth reduction}
}

Keywords: arithmetic circuits, lower bounds, separations, depth reduction
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI