AF: Small: Geometry and Complexity Theory

Abstract

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.