We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:
1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>
The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within \mathrm{P}. In this paper, we study the algebraic formula complexity of multiplying d many 2\times 2 matrices, denoted \mathrm{IMM}_{d}, and show ... more >>>
We study the size blow-up that is necessary to convert an algebraic circuit of product-depth \Delta+1 to one of product-depth \Delta in the multilinear setting.
We show that for every positive \Delta = \Delta(n) = o(\log n/\log \log n), there is an explicit multilinear polynomial P^{(\Delta)} on n variables that ... more >>>
We present a new algorithm for solving homogeneous multilinear equations, which are high dimensional generalisations of solving homogeneous linear equations. First, we present a linear time reduction from solving generic homogeneous multilinear equations to computing hyperdeterminants, via a high dimensional Cramer's rule. Hyperdeterminants are generalisations of determinants, associated with tensors ... more >>>