On minimum witnesses for Boolean matrix multiplication

DOI10.1007/S00453-012-9742-3MaRDI QIDQ517804zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Boolean matrix multiplicationminimum witness

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Boolean and Hadamard matrices (15B34)

Recommendations

• Witnesses for Boolean matrix multiplication and for transitive closure
• An improved algorithm for Boolean matrix multiplication
• scientific article; zbMATH DE number 1256679
• scientific article; zbMATH DE number 1830739
• Fast practical algorithms for the Boolean-product-witness-matrix problem

Cites work

• A New Combinatorial Approach for Sparse Graph Problems
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-pairs bottleneck paths in vertex weighted graphs
• Automata, Languages and Programming
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Fast rectangular matrix multiplication and applications
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Finding heaviest H-subgraphs in real weighted graphs, with applications
• Gaussian elimination is not optimal
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Rectangular matrix multiplication revisited
• Witnesses for Boolean matrix multiplication and for transitive closure

Cited in

(15)

• Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
• 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
• scientific article; zbMATH DE number 1830739 (Why is no real title available?)
• 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.

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)