Some elementary proofs of lower bounds in complexity theory

AbstractWe introduce a new and easily applicable criterion called rank immunity for estimating the minimal number of multiplications needed to compute a set of bilinear forms in commuting variables. The result is obtained by an elimination argument after canonically embedding computations in a quotient ring R/I, where I is an appropriately chosen ideal that is left invariant under the eliminations. The criterion combines the well-known arguments based on elimination and on row rank, but in contrast to (for instance) column- and mixed-rank arguments it normally leads to better elementary estimates than were derivable in a uniform manner before