Algebraic complexity theory and matrix multiplication

By F. Gall. International Symposium on Symbolic and Algebraic Computation, 2014

712 citations recorded by the source corpus.

This tutorial will give an overview of algebraic complexity theory focused on bilinear complexity, and describe several powerful techniques to analyze the complexity of computational problems from linear algebra, in particular matrix multiplication. The presentation of these techniques will follow the history of progress on constructing asymptotically fast algorithms for matrix multiplication, and include its most recent developments.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/dcc1010034ed91753c6e9e4be5cb7987be305874

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Solving linear programs in the current matrix multiplication time (2018, methodology): “Despite the exact approach used in [CW87, Wil12, DS13, LG14] cannot give a bound on ω better than 2 .”
Fast Algorithms for Convolutional Neural Networks (2015, background): “m for fast matrix multiplication to reduce the number of correlations, thereby reducing the total arithmetic complexity of the convnet layer. Using the best known upperbound for matrix multiplication [5], this implies the algorithmic complexity of a convnet layer is less than max(N,C,K)2.3728639 cor”
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (2015, neutral): “6 2.3 Submodular Function Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8”