An improved combinatorial algorithm for Boolean matrix multiplication
From MaRDI portal
Publication:1640996
DOI10.1016/j.ic.2018.02.006zbMath1394.68453arXiv1505.06811OpenAlexW2790642931MaRDI QIDQ1640996
Publication date: 14 June 2018
Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1505.06811
Related Items (21)
Fast Output-Sensitive Matrix Multiplication ⋮ Unnamed Item ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Fast approximation and exact computation of negative curvature parameters of graphs ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ Unnamed Item ⋮ Shortest distances as enumeration problem ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ A fast deterministic detection of small pattern graphs in graphs without large cliques ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing the depth distribution of a set of boxes ⋮ Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs ⋮ Data structures for categorical path counting queries ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication
Cites Work
- Quick approximation to matrices and applications
- General context-free recognition in less than cubic time
- Efficient determination of the transitive closure of a directed graph
- Powers of tensors and fast matrix multiplication
- On the Number of Multiplications Required for Matrix Multiplication
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- Regularity Lemmas and Combinatorial Algorithms
- Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
- Multiplying matrices faster than coppersmith-winograd
- Unnamed Item
- Unnamed Item
This page was built for publication: An improved combinatorial algorithm for Boolean matrix multiplication
