Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-137 | 3rd September 2016 14:37

Finer separations between shallow arithmetic circuits

RSS-Feed




TR16-137
Authors: Mrinal Kumar, Ramprasad Saptharishi
Publication: 3rd September 2016 14:45
Downloads: 1654
Keywords: 


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

1. P_n can be computed by linear sized homogeneous depth-5 circuits.

2. P_n can be computed by poly(n) sized non-homogeneous depth-3 circuits.

3. Any homogeneous depth-4 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 and Vinay[av08, koiran, Tav13] 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 and Saraf [KS14], which showed that the parameters of depth reductions are optimal for algebraic branching programs.



ISSN 1433-8092 | Imprint