Lower bounds on monotone arithmetic circuits with restricted depths (Q1070999)

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.