Sep 18 – 29, 2023
Institut Henri Poincaré
Europe/Paris timezone

Matrix multiplication via Lie groups by Chris Umans

Sep 26, 2023, 9:30 AM
Amphithéâtre Hermite / Darboux (Institut Henri Poincaré)

Amphithéâtre Hermite / Darboux

Institut Henri Poincaré

11 rue Pierre et Marie Curie 75005 Paris


Abstract. 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 ω=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 ω=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.

Presentation materials

There are no materials yet.