AF: Small: Geometry and Complexity Theory

线性代数，包括计算线性方程组的解，是所有科学计算的核心。线性代数的核心运算是矩阵乘法。1968年，V.Strassen发现，被广泛使用并被认为是最好的矩阵乘法算法并不是最优的。从那时起，在开发更好的算法和确定当前算法可以改进的限度方面，人们进行了密集的研究。该项目包括三个部分。前两个是：矩阵乘法算法的实际构造，以及上述限制的确定。第三个问题涉及L.Valiant的一个基本问题，它是著名的P对NP问题的代数模拟。瓦兰特问，一个可以有效写下的多项式是否也必须有一个有效的算法来计算它。所有这三个部分都将使用传统上不用于研究这些问题的理论数学(表示论和代数几何)来探讨。这个项目中算法的实际构建可能会对所有的科学计算产生潜在的影响。理论计算机科学以前没有使用过的现代数学技术的新颖使用将丰富这两个领域，打开数学中的新问题，并为计算机科学提供新的技术。矩阵乘法的指数，表示为欧米伽，是支配线性代数中基本运算的复杂性的基本常数。目前已知的omega在2到2.38之间。与指数无关，实际矩阵乘法(实际产生的大小矩阵的乘法)仅为2.79左右。例如，大小为1000x1000的矩阵可以通过执行(1000)^{2.79}个算术运算来有效地相乘。如果已知实现2.38的omega的算法，则可以使用更少的2.2亿次算术运算来执行相同的矩阵运算。通过利用表示理论，该项目将开发实用的算法，目标是降低这一实用指数。它还将通过分析Strassen的渐近秩猜想及其变体的可行性来解决指数问题，这些猜想提出了证明指数上界的途径。该项目还将解决Valiant关于永久性与决定性的猜想的两个方面。首先，交换代数将被用来改进目前猜想的下界，该猜想自2005年以来一直没有提高过。这位研究人员和一位合著者已经证明了Valiant的猜想在限制的等方差模型下是正确的。第二个方面将调查将这一限制放松到更弱的假设，在这些假设下猜想仍然是可证明的。这一裁决反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Linear algebra, which includes computing the solutions to a system of linear equations, is at the heart of all scientific computation. The core computation of linear algebra is matrix multiplication. In 1968 V. Strassen discovered that the widely used and assumed best algorithm for matrix multiplication is not optimal. Since then there has been intense research in both developing better algorithms and determining the limits of how much the current algorithms can be improved. There are three parts to the project. The first two are: practical construction of algorithms for matrix multiplication, and determining the above-mentioned limits. The third addresses a fundamental question of L. Valiant which is an algebraic analog of the famous P versus NP problem. Valiant asked if a polynomial that can be written down efficiently also must admit an efficient algorithm to compute it. All three parts will be approached using theoretical mathematics not traditionally utilized in the study of these questions (representation theory and algebraic geometry). The practical construction of algorithms in this project could potentially have impact across all scientific computation. The novel use of modern mathematical techniques previously not used in theoretical computer science will enrich both fields, opening new questions in mathematics and providing new techniques to computer science.The exponent of matrix multiplication, denoted omega, is the fundamental constant that governs the complexity of basic operations in linear algebra. It is currently known that omega is somewhere between 2 and 2.38. Independent of the exponent, practical matrix multiplication (of matrices of size that actually arise in practice) is only around 2.79. For example, matrices of size 1000x1000 may be effectively multiplied by performing (1000)^{2.79} arithmetic operations. If algorithms to achieve an omega of 2.38 were known, the same matrix operation can be performed using 220 million fewer arithmetic operations. By exploiting representation theory, this project will develop practical algorithms with the goal of lowering this practical exponent. It will also address the exponent by analyzing the feasibility of Strassen's asymptotic rank conjecture and its variants, which are proposed paths towards proving upper bounds on the exponent. The project will also address two aspects of Valiant's conjecture on permanent versus determinant. First, commutative algebra will be used to improve the current lower bound for the conjecture, which has not advanced since 2005. The investigator and a co-author have proven that Valiant's conjecture is true under the restricted model of equivariance. The second aspect will investigate loosening this restriction to weaker hypotheses under which the conjecture is still provable.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.