Size-depth trade-offs for monotone arithmetic circuits (Q804295)

The paper deals with the size-depth trade-off for monotone arithmetic circuits computing the \(product!a^ TA_ 1...A_ t\cdot b\) where \(A_ 1,...,A_ t\) are \(n\times n\) matrics, a and b are vectors. It is proved that if a monotone circuit computes this product in d parallel multiplication steps and with s multiplications, then \(s+2d(n^ 3-n^ 2)\geq (t+2)n^ 3-2n^ 2+n\). This inequality is tight; a matching upper bound can be achieved for any d in the range \(1+\log t\leq d\leq t/2+1\). In this range, any decrease of one in d requires an increase of \(2(n^ 3- n^ 2)\) in s. It seems extremely hard to obtain similar trade-off for general circuits, i.e. for circuits with the subtraction.