Exact lower bounds for algebraic problems

代数问题的精确下界

• 批准号: 199655955
• 负责人: Professor Dr. Markus Bläser
• 金额: --
• 依托单位: Faculty of Computational Mathematics and Cybernetics
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2011
• 资助国家: 德国
• 起止时间: 2010-12-31 至 2015-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/199655955?language=en
• 关键词: Exact; lower; bounds; 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.

双线性映射的复杂性是代数复杂性理论中的一个重要问题。突出的特殊情况是结合代数中的乘法和矩阵的乘法。该项目的目标是获得某些基本双线性映射的复杂性的精确界。首先，我们要刻画所有代数的Alder-Strassen界是紧的乘法复杂性。其次，我们试图刻画所有代数的双线性复杂性是由一个大于Alder-Strassen界。我们的第三个目标是确定小格式矩阵乘法的精确双线性复杂度，特别是2 x 3与3 x 3矩阵和2 x 2与2 x 4矩阵的乘法。最后，我们将研究一个非常近期和有趣的问题，即测试直线程序是否计算正整数。