On minimum witnesses for Boolean matrix multiplication

DOI10.1007/s00453-012-9742-3zbMath1360.68973OpenAlexW1964042854MaRDI QIDQ517804

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)

Related Items (4)

Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices ⋮ Quantum and approximation algorithms for maximum witnesses of Boolean matrix products ⋮ Extreme Witnesses and Their Applications ⋮ Extreme witnesses and their applications

Cites Work

• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Witnesses for Boolean matrix multiplication and for transitive closure
• Fast rectangular matrix multiplication and applications
• Rectangular matrix multiplication revisited
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Gaussian elimination is not optimal
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• A New Combinatorial Approach for Sparse Graph Problems
• Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
• Multiplying matrices faster than coppersmith-winograd
• Automata, Languages and Programming

This page was built for publication: On minimum witnesses for Boolean matrix multiplication