The Lower Bounds on the Additive Complexity of Bilinear Problems in Terms of Some Algebraic Quantities

摘要

The lower bounds on the additive complexity of a bilinear problem are expressed in terms of the rank of the problem and also as a minimum number of elementary steps for the transformation of the identity matrix into a strongly regular one.