Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Finite matrix multiplication algorithms from infinite groups
IACAPAP ArXiv (Online)
18 Oct 2024
Abstract
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.
Metrics
2 Record Views
Details
- Title
- Finite matrix multiplication algorithms from infinite groups
- Creators
- Jonah BlasiakHenry CohnJoshua A GrochowKevin PrattChris Umans
- Publication Details
- IACAPAP ArXiv (Online)
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021930433704721