Appears in collection : 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of groups as a route to obtaining $\omega=2$, while other families of groups remain potentially viable. In this work we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored. To study these groups, we propose working in the continuous setting of Lie groups, in which we develop an analogous theory. Obtaining the analogue of exponent 2 in this potentially easier setting is a key challenge that represents an intermediate goal short of actually proving $\omega=2$. We give constructions in the continuous setting which are indeed best-possible in a precise sense. We then describe a new ingredient -- "separating polynomials" -- which allow us to recover a full-fledged framework yielding actual (finite) algorithms in the Lie group setting, rather than constructions whose interest is only by analogy. This framework has some mathematically pleasing features: the notion of border rank arises naturally from the Lie algebra, and we have machinery that points to the main open question being that of finding a separating polynomial of appropriate degree in a certain ring of invariant polynomials. This is based on joint work with Jonah Blasiak, Henry Cohn, Josh Grochow, and Kevin Pratt.