Lower Bounds for Non-Commutative Computation (Extended Abstract)
Noam Nisan · 1991
We consider algebraic computations which are not allowed to rely on the commutativity of multiplication. We obtain various lower bounds for algebraic formula size in this model: (1) Computing the determinant is as hard as computing the permanent and tight exponential upper and lower bounds are given. (2) Computation cannot be parallelized, as opposed to in the commutative case -- this solves in the negative an open problem of Miller et al [8]. (3) The question of the power of negation in this model is shown to be closely related to a well known open problem relating communication complexity and rank.