Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products
The problem of finding maximum (or minimum) witnesses of the Boolean product of two Boolean matrices (MW for short) has a number of important applications, in particular the all-pairs lowest common ancestor (LCA) problem in directed acyclic graphs (dags). The best known upper time-bound on the MW problem for n × n Boolean matrices of the form O(n2.575) has not been substantially improved since 200