Kumar, Mrinal ;
Saptharishi, Ramprasad
Finer Separations Between Shallow Arithmetic Circuits
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 depth5 arithmetic circuits,
* P_n can be computed by poly(n) sized nonhomogeneous depth3 arithmetic circuits.
* Any homogeneous depth4 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 [AgrawalVinay 08, Koiran 12, Tavenas 13] are tight for extremely restricted classes of arithmetic circuits, for instance homogeneous depth5 circuits and nonhomogeneous depth3 circuits, and over an appropriate range of parameters, qualitatively improve a result of [KumarSaraf 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 depth4 circuits [KayalLimayeSahaSrinivasan 14, KumarSaraf 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:138:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6873},
URN = {urn:nbn:de:0030drops68730},
doi = {10.4230/LIPIcs.FSTTCS.2016.38},
annote = {Keywords: arithmetic circuits, lower bounds, separations, depth reduction}
}
10.12.2016
Keywords: 

arithmetic circuits, lower bounds, separations, depth reduction 
Seminar: 

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Issue date: 

2016 
Date of publication: 

10.12.2016 