On minimum witnesses for Boolean matrix multiplication
From MaRDI portal
Publication:517804
DOI10.1007/S00453-012-9742-3zbMATH Open1360.68973OpenAlexW1964042854MaRDI QIDQ517804FDOQ517804
Authors: Keren Cohen, Raphael Yuster 
Publication date: 27 March 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9742-3
Recommendations
Cites Work
- Gaussian elimination is not optimal
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Multiplying matrices faster than coppersmith-winograd
- Matrix multiplication via arithmetic progressions
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Fast rectangular matrix multiplication and applications
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Rectangular matrix multiplication revisited
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Witnesses for Boolean matrix multiplication and for transitive closure
- Title not available (Why is that?)
- All-pairs bottleneck paths in vertex weighted graphs
- A New Combinatorial Approach for Sparse Graph Problems
- Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- Automata, Languages and Programming
Cited In (15)
- A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
- Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Witnesses for Boolean matrix multiplication and for transitive closure
- Extreme witnesses and their applications
- Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
- Title not available (Why is that?)
- A New Combinatorial Approach for Sparse Graph Problems
- Fast practical algorithms for the Boolean-product-witness-matrix problem
- Extreme witnesses and their applications
- A fast output-sensitive algorithm for Boolean matrix multiplication
- Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- An improved bound on Boolean matrix multiplication for highly clustered data.
- Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
This page was built for publication: On minimum witnesses for Boolean matrix multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517804)
