Improved bound for complexity of matrix multiplication
The authors give a new bound for the exponents of the complexity of matrix multiplication, based on recursive use of two by two matrix multiplications. It is shown that this new bound is an improvement of previously reported bounds. The exposition in this paper is reasonably concise and self contained. The authors derive the results that they need in this paper from algebraic complexity theory and general background information. The essence if a combinatorial construction that is used in the paper is presented as a lemma. Parts of the argument may be of wider interest outside the algebraic complexity community. References to the articles in the relevant published literature are adequate and extensive.
- Efficient computation of tridiagonal matrices largest eigenvalue
- Geometric adaptive Monte Carlo in random environment
- Fast commutative matrix algorithms
- A linear time algorithm for the nullity of vertex-weighted block graphs
- Parameterized complexity of determinant and permanent
- A numerical solution for Laplace and Poisson's equations using geometrical transformation and graph products
- Allowing cycles in discrete Morse theory
- Lower bounds on the graver complexity of M-fold matrices
- A Lower Bound for Matrix Multiplication
- The xyz algorithm for fast interaction search in high-dimensional data
- Fast matrix multiplication and its algebraic neighbourhood
- On cap sets and the group-theoretic approach to matrix multiplication
- Further limitations of the known approaches for matrix multiplication
- On obtaining upper bounds on the complexity of matrix multiplication
- Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
- Efficient computation of the characteristic polynomial of a threshold graph
- Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
- Slice rank of block tensors and irreversibility of structure tensors of algebras
- Limits on the Universal method for matrix multiplication
- scientific article; zbMATH DE number 7306903 (Why is no real title available?)
- Limits on the universal method for matrix multiplication
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
- Irreversibility of structure tensors of modules
- A nondegenerate \(n\)-dimensional hyperchaotic map model with application in a keyed parallel hash function
- An extended view on lifting Gaussian Bayesian networks
- Efficiently-verifiable strong uniquely solvable puzzles and matrix multiplication
- A refined laser method and faster matrix multiplication
- Combinatorial and recurrent approaches for efficient matrix inversion: sub-cubic algorithms leveraging fast matrix products
- On matrix multiplication and polynomial identity testing
- Bounded simultaneous messages
- Asymptotic spectra: theory, applications, and extensions
- Alternative basis matrix multiplication is fast and \(\mathrm{stable}^\dag\)
This page was built for publication: Improved bound for complexity of matrix multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2837114)
