Multiplying matrices faster than coppersmith-winograd

By Virginia Vassilevska Williams. Symposium on the Theory of Computing, 2012

1,045 citations recorded by the source corpus.

Subfields: Computational Mathematics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/3030fa2aecda339d593b86a260bfab9988b42df7

How researchers see this paper

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

In Computational Mathematics

1. Zhao Song
2. Aaron Sidford
3. Yin Tat Lee
4. Sham M. Kakade
5. F. Gall
6. James B. Orlin
7. Rong Ge
8. Michael B. Cohen

In Computational Theory and Mathematics

1. Yin Tat Lee
2. Aaron Sidford
3. Zhao Song
4. Michael B. Cohen
5. Daniel A. Spielman
6. David P. Woodruff
7. Amir Abboud
8. Shang-Hua Teng

Citations in the corpus

• Max flows in O(nm) time, or better (2013, methodology): “This running time was developed by Williams [24].”
• Algebraic complexity theory and matrix multiplication (2014, methodology): “3729 in the most recent version [16], since the previous bound omi tted some necessary constraints in the optimization problem.”
• 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 .”
• Low rank approximation with entrywise l1-norm error (2017, neutral): “373 is the matrix multiplication exponent[30, 85, 88].”
• Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow (2014, neutral): “3729 [47] is the matrix multiplication constant.”
• Multiple‐Robot Simultaneous Localization and Mapping: A Review (2016, neutral): “373) (Virginia Vassilevska Williams, 2012).”
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth (2013, neutral): “3727 [24]).”
• Exact controllability of complex networks (2013, neutral): “DOI: 10.1038/ncomms3447 OPEN”
• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems (2006, methodology): “We remark that the algorithm of Lipton, Rose, and Tarjan [43] can be accelerated by the use of algorithms for fast matrix inversion [18, 50, 60].”
• A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (2015, neutral): “6 2.3 Submodular Function Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8”
• Subcubic Equivalences between Path, Matrix and Triangle Problems (2010, background): “373) [48], which together with an independent result by Stothers [ 41] recently improved on the longstanding bound of O(n2.”
• Randomized Matrix Computations (2012, neutral): “The latter paper has introduced the technique of trilinear aggregation, a basic ingredient of all subsequent fast algorithms for matrix multiplication with the inputs of both immense sizes (far beyond any practical interest) [P79], [P81], [P84], [CW90], [S10], [VW12] and realistic moderate sizes [P8”
• Measuring user influence on Twitter: A survey (2015, background): “3727 ) time [26,145], and maybe little faster.”
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization (2015, background): “Both in theory and in practice, the provided algorithms reap the computational benefits of adding a large strongly convex regularization term, without incurring a corresponding bias to the original problem.”
• Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems (2014, background): “373 is the matrix multiplication exponent [36], [15], [10], [11].”