Classical results of Brent, Kuck and Maruyama (IEEE Trans.Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth Oplog sq with only a polynomial blow-up in size.In this paper, we consider a fine-grained version of this result depending on the degree of the polynomial computed by the algebraic formula.Given a homogeneous algebraic formula of size s computing a polynomial P of degree d, we show that P can also be computed by an (unbounded fan-in) algebraic formula of depth Oplog dq and size polypsq.Our proof shows that this result also holds in the highly restricted setting of monotone, non-commutative algebraic formulas.This improves on previous results in the regime when d is small (i.e., d " s op1q ).In particular, for the setting of d " Oplog sq, along with a result of Raz (STOC 2010, JACM 2013), our result implies the same depth reduction even for inhomogeneous formulas.This is particularly interesting in light of recent algebraic formula lower bounds, which work precisely in this "low-degree" and "low-depth" setting.We also show that these results cannot be improved in the monotone setting, even for commutative formulas.

Inspired by Nisan’s characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove a rather tight lower bound for the computation of elementary symmetric polynomials by algebraic branching programs in the monotone setting or, equivalently, in the homogeneous syntactically multilinear setting.

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth-4 arithmetic formula computing the product of $d$ generic matrices of size $n \times n$, $\mathrm{IMM}_{n,d}$, has size $n^{\Omega(\sqrt{d})}$ as long as $d = n^{O(1)}$. This improves the result of Nisan and Wigderson [Comput. Complexity, 6 (1997), pp. 217--234] for depth-4 set-multilinear formulas. We also study $\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}$ formulas, which are depth-4 formulas with the stated bounds on the fan-ins of the $\Pi$ gates. A recent depth reduction result of Tavenas [Lecture Notes in Comput. Sci. 8087, 2013, pp. 813--824] shows that any $n$-variate degree $d = n^{O(1)}$ polynomial computable by a circuit of size $\mathop{\mathrm{poly}}(n)$ can also be computed by a depth-4 $\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}$ formula of top fan-in $n^{O(d/t)}$. We show that any such formula computing $\mathrm{IMM}_{n,d}$ has top fan-in $n^{\Omega({d/t})}$, proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi [Proceedings of STOC, 2014, pp. 146--153], which gives a similar lower bound for an explicit polynomial in VNP.

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant of a matrix of polynomially bounded size. Strikingly, this restatement does not mention any notion of computational model. To get a similar restatement for the original and more fundamental question, and also to better understand the class itself, we need a complete polynomial for VP. Ad hoc constructions yielding complete polynomials were known, but not natural examples in the vein of the determinant. We give here several variants of natural complete polynomials for VP, based on the notion of graph homomorphism polynomials.

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n, IMMn,d, has size nΩ(√d) as long as d = nO(1). This improves the result of Nisan and Wigderson (Computational Complexity, 1997) for depth 4 set-multilinear formulas.

We consider the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of monomials. We show that these problems are complete for subclasses of the counting hierarchy which had few or no known natural complete problems. We also study these questions for circuits computing multilinear polynomials.

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of multilinear ABPs to that of multilinear arithmetic formulas, and prove a tight super-polynomial separation between the two models. Specifically, we describe an explicit n-variate polynomial F that is computed by a linear-size multilinear ABP but every multilinear formula computing F must be of size nΩ(log n).

We study the link between the complexity of a polynomial and that of its coefficient functions. Valiant's theory is a good setting for this, and we start by generalizing one of Valiant's observations, showing that the class VNP is stable for coefficient functions, and that this is true of the class VP iff VP=VNP, an eventuality which would be as surprising as the equality of the classes P and NP in Boolean complexity. We extend the definition of Valiant's classes to polynomials of unbounded degree, thus defining the classes VPnband VNPnb. Over rings of positive characteristic the same kind of results hold in this case, and we also prove that VP=VNP iff VPnb=VNPnb. Finally, we use our extension of Valiant's results to show that iterated partial derivatives can be efficiently computed iff VP=VNP. This is also true for the case of polynomials of unbounded degree, if the characteristic of the ring is positive.