Exact lower bounds for algebraic problems

• Applicant: Professor Dr. Markus Bläser
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 199655955

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.

• DFG Programme: Research Grants
• International Connection: Russia
• Participating Person: Professor Dr. Valeriy Alekseev