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

We consider the famous Strassen algorithm for fast multiplication of matrices. We show that this algorithm has a nontrivial finite group of automorphisms of order 36 (namely the direct product of two copies of the symmetric group on 3 symbols), or even 72, if we consider "extended" Strassen algorithm. This is an indirect evidence that the (unknown at present) optimal algorithm for multiplication of two size 3 by 3 matrices also may have a large automorphism group, and this ma...

We establish bounds for the representation dimension of skew group algebras and wreath products. Using this, we obtain bounds for the representation dimension of a block of a Hecke algebra of type A, in terms of the weight of the block. This includes certain blocks of group algebras of symmetric groups.

One of prospective ways to find new fast algorithms of matrix multiplication is to study algorithms admitting nontrivial symmetries. In the work possible algorithms for multiplication of $3\times3$ matrices, admitting a certain group $G$ isomorphic to $S_4\times S_3$, are investigated. It is shown that there exist no such algorithms of length $\leq23$. In the first part of the work, which is the content of the present article, we describe all orbits of length $\leq23$ of $G$ ...

This is an overview of recent developments regarding the complexity of matrix multiplication, with an emphasis on the uses of algebraic geometry and representation theory in complexity theory.

We survey results in algebraic complexity theory, focusing on matrix multiplication. Our goals are (i.) to show how open questions in algebraic complexity theory are naturally posed as questions in geometry and representation theory, (ii.) to motivate researchers to work on these questions, and (iii.) to point out relations with more general problems in geometry. The key geometric objects for our study are the secant varieties of Segre varieties. We explain how these variet...

In this work the algorithms of fast multiplication of matrices are considered. To any algorithm there associated a certain group of automorphisms. These automorphism groups are found for some well-known algorithms, including algorithms of Hopcroft, Laderman, and Pan. The automorphism group is isomorphic to $S_3\times Z_2$ and $S_4$ for Hopcroft anf Laderman algorithms, respectively. The studying of symmetry of algorithms may be a fruitful idea for finding fast algorithms, by ...

We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a generalization based on zeroing outs which subsumes these two approaches, which we call the Solar method, and an even more general method based on monomial degenerations, which we call the Galactic method. We then design a suite of techniques for proving lower bounds on the val...

Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives and brought us some beautiful formulas and combinatorial interpretations. The flagship hook-length formula counts the number of Standard Young Tableaux, which also gives the dimension of the irreducible Specht modules of the Symmetric group. The elegant Littlew...

This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic constructions also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches, this method is based on convex optimization, and thus has polynomial-time complexity. As an application, we use this method to study powers of the construction given by Coppersmith and Winograd [Journal of Symbolic Computati...

This paper introduces and develops a general framework for studying triple factorisations of the form $G=ABA$ of finite groups $G$, with $A$ and $B$ subgroups of $G$. We call such a factorisation nondegenerate if $G\neq AB$. Consideration of the action of $G$ by right multiplication on the right cosets of $B$ leads to a nontrivial upper bound for $|G|$ by applying results about subsets of restricted movement. For $A<C<G$ and $B<D<G$ the factorisation $G=CDC$ may be degenerate...