The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication

Mulmuley and Sohoni (GCT1 in SICOMP 2001, GCT2 in SICOMP 2008) proposed to view the permanent versus determinant problem as a specific orbit closure problem and to attack it by methods from geometric invariant and representation theory. We adopt these ideas towards the goal of showing lower bounds on the border rank of specific tensors, in particular for matrix multiplication. We thus study specific orbit closure problems for the group $G = GL(W_1)\times GL(W_2)\times GL(W_3)...

Studying algorithms admitting nontrivial symmetries is a prospective way of constructing new short algorithms of matrix multiplication. The main result of the article is that if there exists an algorithm of multiplicative length $l\leq22$ for multuplication of $3\times3$ matrices then its automorphism group is isomorphic to a subgroup of $S_l\times S_3$.

We study the growth of product sets in some finite three-dimensional matrix groups. In particular, we prove two results about the group of $2\times 2$ upper triangular matrices over arbitrary finite fields: a product set estimate using techniques from multiplicative combinatorics, and an energy estimate using incidence geometry. The energy method gives better quantitative results, but only applies to small sets. We also prove an energy result for the Heisenberg group.

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 \leq 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 u...

We introduce an algorithm to decompose orthogonal matrix representations of the symmetric group over the reals into irreducible representations, which as a by-product also computes the multiplicities of the irreducible representations. The algorithm applied to a $d$-dimensional representation of $S_n$ is shown to have a complexity of $O(n^2 d^3)$ operations for determining multiplicities of irreducible representations and a further $O(n d^4)$ operations to fully decompose rep...

This paper studies geometric properties of the Iterated Matrix Multiplication polynomial and the hypersurface that it defines. We focus on geometric aspects that may be relevant for complexity theory such as the symmetry group of the polynomial, the dual variety and the Jacobian loci of the hypersurface, that are computed with the aid of representation theory of quivers.

In this work, we prove limitations on the known methods for designing matrix multiplication algorithms. Alman and Vassilevska Williams recently defined the Universal Method, which substantially generalizes all the known approaches including Strassen's Laser Method and Cohn and Umans' Group Theoretic Method. We prove concrete lower bounds on the algorithms one can design by applying the Universal Method to many different tensors. Our proofs use new tools for upper bounding the...

Fast matrix-by-matrix multiplication (hereafter MM) is a highly recognized research subject. The record upper bound 3 of 1968 on the exponent of the complexity MM decreased below 2.38 by 1987, applies to celebrated problems in many areas of computing, and is extensively cited in the Theory of Computing. Further decrease of the exponent remains a celebrated challenge. Acceleration of MM in the Practice of Computing is a distinct challenge, because all known algorithms supporti...

For fixed compact connected Lie groups H \subseteq G, we provide a polynomial time algorithm to compute the multiplicity of a given irreducible representation of H in the restriction of an irreducible representation of G. Our algorithm is based on a finite difference formula which makes the multiplicities amenable to Barvinok's algorithm for counting integral points in polytopes. The Kronecker coefficients of the symmetric group, which can be seen to be a special case of su...

It is proved that there is no an algorithm for multiplication of $3\times3$ matrices of multiplicative length $\leq23$ that is invariant under a certain group isomorphic to $S_4\times S_3$. The proof makes use of description of the orbits of this group on decomposable tensors in the tensor cube $(M_3({\mathbb C}))^{\otimes3}$ which was obtained earlier.