Multiplying matrices faster than coppersmith-winograd
From MaRDI portal
Publication:5415522
DOI10.1145/2213977.2214056zbMath1286.65056DBLPconf/stoc/Williams12OpenAlexW2038073775WikidataQ55924219 ScholiaQ55924219MaRDI QIDQ5415522
Publication date: 13 May 2014
Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2213977.2214056
Related Items (only showing first 100 items - show all)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Universal points in the asymptotic spectrum of tensors ⋮ On the Combinatorial Power of the Weisfeiler-Lehman Algorithm ⋮ Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices ⋮ Faster 2-Disjoint-Shortest-Paths Algorithm ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Deterministic Truncation of Linear Matroids ⋮ How to Compute in the Presence of Leakage ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ Memory-Efficient Sparse Matrix-Matrix Multiplication by Row Merging on Many-Core Architectures ⋮ Fast Output-Sensitive Matrix Multiplication ⋮ Unnamed Item ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Extreme Witnesses and Their Applications ⋮ Network-Based Dissolution ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ New applications of the polynomial method: The cap set conjecture and beyond ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Maximal and Maximum Transitive Relation Contained in a Given Binary Relation ⋮ Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ Simultaneous feedback edge set: a parameterized perspective ⋮ On the tensor rank of $3\times 3$ permanent and determinant ⋮ Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps ⋮ Efficiently Correcting Matrix Products ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ On Dynamic DFS Tree in Directed Graphs ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Reverse-Safe Text Indexing ⋮ Constructive Packings of Triple Systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Superquadratic Variant of Newton's Method ⋮ Unnamed Item ⋮ Detecting the large entries of a sparse covariance matrix in sub-quadratic time ⋮ Hardness Results for Structured Linear Systems ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ On computing the Hamiltonian index of graphs ⋮ Computing the rooted triplet distance between galled trees by counting triangles ⋮ A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ On the inequivalence of bilinear algorithms for \(3\times 3\) matrix multiplication ⋮ Fast monotone summation over disjoint sets ⋮ A note on probabilistic models over strings: the linear algebra approach ⋮ Border Rank Is Not Multiplicative under the Tensor Product ⋮ Faster Algorithms for Weighted Recursive State Machines ⋮ Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution ⋮ Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model ⋮ Further Limitations of the Known Approaches for Matrix Multiplication ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. ⋮ Improved Time and Space Bounds for Dynamic Range Mode ⋮ On cap sets and the group-theoretic approach to matrix multiplication ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hanani-Tutte for approximating maps of graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication lower bounds and optimal algorithms for numerical linear algebra ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Counting points on curves using a map to $\mathbf {P}^1$ ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ The role of planarity in connectivity problems parameterized by treewidth ⋮ A comparative analysis of the successive lumping and the lattice path counting algorithms ⋮ Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Limits on the Universal method for matrix multiplication ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ Unnamed Item ⋮ Faster Algorithms for All Pairs Non-Decreasing Paths Problem ⋮ Upgrading Subgroup Triple-Product-Property Triples ⋮ On the Differential and Full Algebraic Complexities of Operator Matrices Transformations ⋮ Editing to Connected F-Degree Graph ⋮ Barriers for fast matrix multiplication from irreversibility ⋮ Border Rank Nonadditivity for Higher Order Tensors ⋮ Computation of polarized metrized graph invariants by using discrete Laplacian matrix ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Network-Based Vertex Dissolution ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Unnamed Item ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dominance Product and High-Dimensional Closest Pair under L_infty ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
This page was built for publication: Multiplying matrices faster than coppersmith-winograd
