History

Please fill in your query. A complete syntax description you will find on the General Help page.
A complete characterization of the algebras of minimal bilinear complexity. (English)
SIAM J. Comput. 34, No. 2, 277-298 (2004).
Summary: Let $R(A)$ denote the rank (also called bilinear complexity) of a finite-dimensional associative algebra $A$. A fundamental lower bound for $R(A)$ is the so-called Alder-Strassen bound $R(A) \ge 2 \dim A-t$, where $t$ is the number of maximal two-sided ideals of $A$. An algebra is called an algebra of minimal rank if the Alder-Strassen bound is tight, i.e., $R(A) = 2 \dim A-t.$ As the main contribution of this work, we characterize all algebras of minimal rank over arbitrary fields. This finally solves an open problem in algebraic complexity theory [see, for instance, {\it V. Strassen}, “Algebraic complexity theory", in: J. van Leeuwen (ed.), Handbook of theoretical computer science. Vol. A. Algorithms and complexity. Amsterdam: Elsevier; Cambridge, MA: MIT Press, 633‒672 (1990; Zbl 0712.68054), Section 12, Problem 4, or {\it P. Bürgisser, M. Clausen}, and {\it M. A. Shokrollahi}, Algebraic complexity theory. Berlin: Springer (1997; Zbl 1087.68568), Problem 17.5].