TY - JOUR T1 - Lower bounds on monotone arithmetic circuits with restricted depths JF - Computers & Mathematics with Applications Y1 - 1985 A1 - JaJa, Joseph F. AB - We consider monotone arithmetic circuits with restricted depths to compute monotone multivariate polynomials such as the elementary symmetric functions, convolution of several vectors and raising a matrix to a power. We develop general lower- and upper-bound techniques that seem to generate almost-matching bounds for all the functions considered. These results imply exponential lower bounds for circuits of bounded depths which compute any of these functions. We also obtain several examples for which negation can reduce the size exponentially. VL - 11 SN - 0898-1221 UR - http://www.sciencedirect.com/science/article/pii/0898122185901038 CP - 12 M3 - 10.1016/0898-1221(85)90103-8 ER -