Determining the asymptotic algebraic complexity of matrix multiplication, succinctly represented by the matrix multiplication exponent omega, is a central problem in algebraic complexity theory. The best upper bounds on omega, leading to the state-of-the-art omega <= 2.37.., have been obtained via the laser method of Strassen and its generalization by Coppersmith and Winograd. Recent barrier results show limitations for these and related approaches to improve the upper bound on omega. We introduce a new and more general barrier, providing stronger limitations than in previous work. Concretely, we introduce the notion of "irreversibility" of a tensor and we prove (in some precise sense) that any approach that uses an irreversible tensor in an intermediate step (e.g., as a starting tensor in the laser method) cannot give omega = 2. In quantitative terms, we prove that the best upper bound achievable is lower bounded by two times the irreversibility of the intermediate tensor. The quantum functionals and Strassen support functionals give (so far, the best) lower bounds on irreversibility. We provide lower bounds on the irreversibility of key intermediate tensors, including the small and big Coppersmith - Winograd tensors, that improve limitations shown in previous work. Finally, we discuss barriers on the group-theoretic approach in terms of "monomial" irreversibility.
more »
« less
Matrix Multiplication via Matrix Groups
In 2003, 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 paper we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored.
We first show that groups of Lie type cannot prove ω = 2 within the group-theoretic approach. This is based on a representation-theoretic argument that identifies the second-smallest dimension of an irreducible representation of a group as a key parameter that determines its viability in this framework. Our proof builds on Gowers' result concerning product-free sets in quasirandom groups. We then give another barrier that rules out certain natural matrix group constructions that make use of subgroups that are far from being self-normalizing.
Our barrier results leave open several natural paths to obtain ω = 2 via matrix groups. To explore these routes we propose working in the continuous setting of Lie groups, in which we develop an analogous theory. Obtaining the analogue of ω = 2 in this potentially easier setting is a key challenge that represents an intermediate goal short of actually proving ω = 2. We give two constructions in the continuous setting, each of which evades one of our two barriers.
more »
« less
- Award ID(s):
- 2047756
- PAR ID:
- 10401771
- Editor(s):
- Tauman Kalai, Yael
- Date Published:
- Journal Name:
- Leibniz international proceedings in informatics
- Volume:
- 251
- ISSN:
- 1868-8969
- Page Range / eLocation ID:
- 19
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously known barriers, both in the numerical sense, as well as in its generality. We prove our result using the asymptotic spectrum of tensors. More precisely, we crucially make use of two families of real tensor parameters with special algebraic properties: the quantum functionals and the support functionals. In particular, we prove that any lower bound on the dual exponent of matrix multiplication α via the big Coppersmith–Winograd tensors cannot exceed 0.625.more » « less
-
Bellaïche has recently applied Pink-Lie theory to prove that, under mild conditions, the image of a continuous 2-dimensional pseudorepresentation ρ of a profinite group on a local pro- p domain A contains a nontrivial congruence subgroup of SL2(B) for a certain subring B of A. We enlarge Bellaïche’s ring and give this new B a conceptual interpretation both in terms of conjugate self-twists of ρ, symmetries that constrain its image, and in terms of the adjoint trace ring of ρ, which we show is both more natural and the optimal ring for these questions in general. Finally, we use our purely algebraic result to recover and extend a variety of arithmetic big-image results for GL2-Galois representations arising from elliptic, Hilbert, and Bianchi modular forms and p-adic Hida or Coleman families of elliptic and Hilbert modular forms.more » « less
-
A tensor network is a diagram that specifies a way to "multiply" a collection of tensors together to produce another tensor (or matrix). Many existing algorithms for tensor problems (such as tensor decomposition and tensor PCA), although they are not presented this way, can be viewed as spectral methods on matrices built from simple tensor networks. In this work we leverage the full power of this abstraction to design new algorithms for certain continuous tensor decomposition problems. An important and challenging family of tensor problems comes from orbit recovery, a class of inference problems involving group actions (inspired by applications such as cryo-electron microscopy). Orbit recovery problems over finite groups can often be solved via standard tensor methods. However, for infinite groups, no general algorithms are known. We give a new spectral algorithm based on tensor networks for one such problem: continuous multi-reference alignment over the infinite group SO(2). Our algorithm extends to the more general heterogeneous case.more » « less
-
more » « less
Double groupoids are a type of higher groupoid structure that can arise when one has two distinct groupoid products on the same set of arrows. A particularly important example of such structures is the irrational torus and, more generally, strict 2-groups. Groupoid structures give rise to convolution operations on the space of arrows. Therefore, a double groupoid comes equipped with two product operations on the space of functions. In this article we investigate in what sense these two convolution operations are compatible. We use the representation theory of compact Lie groups to get insight into a certain class of 2-groups.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
