Exact lower bounds for algebraic problems

• Antragsteller: Professor Dr. Markus Bläser
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Sachbeihilfen
• Internationaler Bezug: Russische Föderation
• Beteiligte Person: Professor Dr. Valeriy Alekseev