Exact lower bounds for algebraic problems

点击翻译按钮获取中文摘要

The complexity of bilinear mappings is an important problem in algebraic complexity theory. Prominent special cases are the multiplicaton in associative algebras and the multiplication of matrices. The goal of the proposed project is to obtain exact bounds on the complexity of certain fundamental bilinear maps. First of all, we want to characterize all algebras for which the Alder-Strassen bound is tight for the multiplicative complexity. Second, we attempt to characterize all algebras the bilinear complexity of which is by one larger than the Alder-Strassen bound. Our third goal is to determine the exact bilinear complexity of the multiplication of matrices of small formats, in particular of the multiplication of 2 x 3 with 3 x 3 matrices and of 2 x 2 with 2 x 4 matrices. Finally, we will investigate a very recent and interesting problem, namely, testing whether a straightline program computes a positive integer.