The Cohn-Umans (FOCS '03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group G satisfying a simple combinatorial condition (the Triple Product Property). The complexity of such an algorithm then depends on the representation theory of G. In this paper we extend the group-theoretic framework to the setting of infinite groups. In particular, this allows us to obtain constructions in Lie groups, with favorable parameters, that are provably impossible in finite groups of Lie type (Blasiak, Cohn, Grochow, Pratt, and Umans, ITCS '23). Previously the Lie group setting was investigated purely as an analogue of the finite group case; a key contribution in this paper is a fully developed framework for obtaining bona fide matrix multiplication algorithms directly from Lie group constructions. As part of this framework, we introduce "separating functions" as a necessary new design component, and show that when the underlying group is G = GL_n, these functions are polynomials with their degree being the key parameter. In particular, we show that a construction with "half-dimensional" subgroups and optimal degree would imply ω = 2. We then build up machinery that reduces the problem of constructing optimal-degree separating polynomials to the problem of constructing a single polynomial (and a corresponding set of group elements) in a ring of invariant polynomials determined by two out of the three subgroups that satisfy the Triple Product Property. This machinery combines border rank with the Lie algebras associated with the Lie subgroups in a critical way. We give several constructions illustrating the main components of the new framework, culminating in a construction in a special unitary group that achieves separating polynomials of optimal degree, meeting one of the key challenges. The subgroups in this construction have dimension approaching half the ambient dimension, but (just barely) too slowly. We argue that features of the classical Lie groups make it unlikely that constructions in these particular groups could produce nontrivial bounds on ω unless they prove ω = 2. One way to get ω = 2 via our new framework would be to lift our existing construction from the special unitary group to GL_n, and improve the dimension of the subgroups from (dim G)/2 - Θ(n) to (dim G)/2 - o(n).

We study a discrete model of repelling particles, and we show using linear programming bounds that many familiar families of error-correcting codes minimize a broad class of potential energies when compared with all other codes of the same size and block length. Examples of these universally optimal codes include Hamming, Golay, and Reed-Solomon codes, among many others, and this helps to explain their robustness as the channel model varies. Universal optimality of these codes is equivalent to minimality of their binomial moments, which has been proved in many cases by Ashikhmin and Barg. We highlight connections with mathematical physics and the analogy between these results and previous work by Cohn and Kumar in the continuous setting, and we develop a framework for optimizing the linear programming bounds. Furthermore, we show that if these bounds prove a code is universally optimal, then the code remains universally optimal even if one codeword is removed.

No abstract available.

We introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s-rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the “s-rank exponent of matrix multiplication” equals 2, then ω = 2. This connection between the s-rank exponent and the ordinary exponent enables us to significantly generalize the group-theoretic approach of Cohn and Umans, from group algebras to general algebras. Embedding matrix multiplication into general algebra multiplication yields bounds on s-rank (not ordinary rank) and, prior to this paper, that had been a barrier to working with general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. Coherent configurations are combinatorial objects that generalize groups and group actions; adjacency algebras are the analogue of group algebras and retain many of their important features. As with groups, coherent configurations support matrix multiplication when a natural combinatorial condition is satisfied, involving triangles of points in their underlying geometry. Finally, we prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on ω using commutative coherent configurations and suggests that commutative coherent configurations may be sufficient to prove ω = 2. Altogether, our results show that bounds on ω can be established by embedding large matrix multiplication instances into small commutative coherent configurations.

We further develop the group-theoretic approach to fast matrix multiplication introduced by Cohn and Umans, and for the first time use it to derive algorithms asymptotically faster than the standard algorithm. We describe several families of wreath product groups that achieve matrix multiplication exponent less than 3, the asymptotically fastest of which achieves exponent 2.41. We present two conjectures regarding specific improvements, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.

We develop a new, group-theoretic approach to bounding the exponent of matrix multiplication. There are two components to this approach: (1) identifying groups G that admit a certain type of embedding of matrix multiplication into the group algebra /spl Copf/[G], and (2) controlling the dimensions of the irreducible representations of such groups. We present machinery and examples to support (1), including a proof that certain families of groups of order n/sup 2+o(1)/ support n /spl times/ n matrix multiplication, a necessary condition for the approach to yield exponent 2. Although we cannot yet completely achieve both (1) and (2), we hope that it may be possible, and we suggest potential routes to that result using the constructions in this paper.