Multiplying matrices faster than coppersmith-winograd
From MaRDI portal
Publication:5415522
DOI10.1145/2213977.2214056zbMath1286.65056OpenAlexW2038073775WikidataQ55924219 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
Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings, Polly cracker, revisited, Quantum and approximation algorithms for maximum witnesses of Boolean matrix products, On the nuclear norm and the singular value decomposition of tensors, Beyond the BEST theorem: fast assessment of Eulerian trails, Optimal approximation algorithms for maximum distance-bounded subgraph problems, Deterministic parameterized algorithms for the graph motif problem, On interval decomposability of \(2\)D persistence modules, Rural postman parameterized by the number of components of required edges, An improved combinatorial algorithm for Boolean matrix multiplication, A latent variable model for two-dimensional canonical correlation analysis and the variational inference, Bounds on complexity of matrix multiplication away from Coppersmith-Winograd tensors, Improving quantum query complexity of Boolean matrix multiplication using graph collision, Triangle counting in dynamic graph streams, Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane, Structure of squares and efficient domination in graph classes, Fast commutative matrix algorithms, On the arithmetic complexity of Strassen-like matrix multiplications, Counting points on curves using a map to \(\mathbf P^1\). II., On the word problem for special monoids, On sunflowers and matrix multiplication, Guarding orthogonal art galleries with sliding cameras, Modular composition modulo triangular sets and applications, Finding even subgraphs even faster, On computing an optimal semi-matching, An introduction to the computational complexity of matrix multiplication, Efficiently correcting matrix products, A complete greedy algorithm for infinite-horizon sensor scheduling, Sunflowers and testing triangle-freeness of functions, On enumerating monomials and other combinatorial structures by polynomial interpolation, Parsing by matrix multiplication generalized to Boolean grammars, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), Parameterized complexity of conflict-free matchings and paths, A scalable approach to computing representative lowest common ancestor in directed acyclic graphs, Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back, Induced subgraph isomorphism: are some patterns substantially easier than others?, Computing mixed volume and all mixed cells in quermassintegral time, The number of Euler tours of random directed graphs, A new coding-based algorithm for finding closest pair of vectors, Simple realizability of complete abstract topological graphs simplified, Clustered planarity testing revisited, Improvements to the deformation method for counting points on smooth projective hypersurfaces, \(c\)-planarity of embedded cyclic \(c\)-graphs, Computing the Fréchet distance between folded polygons, A simple approach to nondecreasing paths, Weighted efficient domination in two subclasses of \(P_6\)-free graphs, Plethysm and fast matrix multiplication, Fast structured matrix computations: tensor rank and Cohn-Umans method, Rank-profile revealing Gaussian elimination and the CUP matrix decomposition, Guessing singular dependencies, New exact algorithms for the 2-constraint satisfaction problem, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, Fooling views: a new lower bound technique for distributed computations under congestion, Speeding-up verification of digital signatures, Clifford algebras meet tree decompositions, Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs, Relaxed Hensel lifting of triangular sets, Towards a geometric approach to Strassen's asymptotic rank conjecture, New ways to multiply \(3 \times 3\)-matrices, Efficient algorithms for subgraph listing, Work-sensitive dynamic complexity of formal languages, A fast deterministic detection of small pattern graphs in graphs without large cliques, Mutually unbiased weighing matrices, A review of two network curvature measures, Algorithms and conditional lower bounds for planning problems, Efficient computation of the characteristic polynomial of a threshold graph, Numerical CP decomposition of some difficult tensors, Inverse linear difference operators, Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth, Revealed preference theory: an algorithmic outlook, Further remarks on DNA overlap assembly, Fast bilinear algorithms for symmetric tensor contractions, On minimum witnesses for Boolean matrix multiplication, A \(\min\)-\(\max\) relation in flowgraphs and some applications, Approximating the minimum cycle mean, Dynamic matrix rank with partial lookahead, Linear-space data structures for range mode query in arrays, Caps and progression-free sets in \(\mathbb{Z}_m^n\), Parsing Boolean grammars over a one-letter alphabet using online convolution, Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification, Path querying on acyclic graphs using Boolean grammars, Two-dimensional pattern matching against local and regular-like picture languages, Efficient domination for classes of \(P_6\)-free graphs, Sparse matrix multiplication and triangle listing in the congested clique model, Extreme witnesses and their applications, Rank and border rank of Kronecker powers of tensors and Strassen's laser method, Exact and approximation algorithms for weighted matroid intersection, Data structures for categorical path counting queries, Grothendieck constant is norm of Strassen matrix multiplication tensor, Variations on the bottleneck paths problem, On the complexity of the \(F_5\) Gröbner basis algorithm, Chinese remainder theorem for cyclotomic polynomials in \(\mathbb Z[X\)], Computing the Gromov hyperbolicity of a discrete metric space, Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs, On the implementation efficiency of linear regression-based side-channel attacks, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Random matrices over a DVR and LU factorization, Unifying known lower bounds via geometric complexity theory, Tensor-product-Thomas elliptic solver for liquid-metal magnetohydrodynamics, A fast parallel algorithm for minimum-cost small integral flows, Counting Subgraphs in Degenerate Graphs, Short Communication: Exponential Utility Maximization in a Discrete Time Gaussian Framework, Skew-polynomial-sparse matrix multiplication, Counting Homomorphic Cycles in Degenerate Graphs, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, Enumerating grammar-based extractions, Towards Practical Fast Matrix Multiplication based on Trilinear Aggregation, Alternative fan-beam backprojection and adjoint operators, Pebbling Game and Alternative Basis for High Performance Matrix Multiplication, Unnamed Item, Internal masked prefix sums and its connection to fully internal measurement queries, Fine-Grained Complexity of Regular Path Queries, Batched fully dynamic multi-key FHE from FHEW-like cryptosystems, Improved Merlin-Arthur protocols for central problems in fine-grained complexity, Unnamed Item, Unnamed Item, On the Parameterized Complexity of Clique Elimination Distance, Detecting and Counting Small Pattern Graphs, Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation), Parameterized algorithms for module map problems, Fast exact algorithms for survivable network design with uniform requirements, Parameterized complexity of geometric covering problems having conflicts, Rare siblings speed-up deterministic detection and counting of small pattern graphs, Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones, Quantum discriminant analysis for dimensionality reduction and classification, Graph Classes and Forbidden Patterns on Three Vertices, Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles, Elastic-Degenerate String Matching via Fast Matrix Multiplication, Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication, A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix, 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
