Pith. sign in

REVIEW 1 cited by

Finite matrix multiplication algorithms from infinite groups

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2410.14905 v2 pith:SQYZZIEX submitted 2024-10-18 math.GR cs.DS

Jonah Blasiak , Henry Cohn , Joshua A. Grochow , Kevin Pratt , Chris Umans This is my paper · ORCID
classification math.GRcs.DS
keywords finitegroupgroupsmatrixmultiplicationalgorithmsframeworkconstructions
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Asymptotic tensor rank is characterized by polynomials

    cs.CC 2024-11 conditional novelty 8.0 of 10

    Sublevel sets of asymptotic tensor rank are Zariski-closed, making the parameter well-ordered in value, complete over the complex numbers, and computable from above.

Pith tools