Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products
(2021) 7th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2021 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12601 LNCS. p.440451 Abstract
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 allpairs lowest common ancestor (LCA) problem in directed acyclic graphs (dags). The best known upper timebound on the MW problem for n× n Boolean matrices of the form O(n^{2.575}) has not been substantially improved since 2006. In order to obtain faster algorithms for this problem, we study quantum algorithms for MW and approximation algorithms for MW (in the standard computational model). Some of our quantum algorithms are input or output sensitive. Our fastest quantum algorithm for the MW problem, and consequently for the related problems, runs in time... (More)
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 allpairs lowest common ancestor (LCA) problem in directed acyclic graphs (dags). The best known upper timebound on the MW problem for n× n Boolean matrices of the form O(n^{2.575}) has not been substantially improved since 2006. In order to obtain faster algorithms for this problem, we study quantum algorithms for MW and approximation algorithms for MW (in the standard computational model). Some of our quantum algorithms are input or output sensitive. Our fastest quantum algorithm for the MW problem, and consequently for the related problems, runs in time O~ (n^{2} ^{+} ^{λ} ^{/} ^{2}) = O~ (n^{2.434}), where λ satisfies the equation ω(1,λ,1)=1+1.5λ and ω(1, λ, 1 ) is the exponent of the multiplication of an n× n^{λ} matrix by an n^{λ}× n matrix. Next, we consider a relaxed version of the MW problem (in the standard model) asking for reporting a witness of bounded rank (the maximum witness has rank 1) for each nonzero entry of the matrix product. First, by adapting the fastest known algorithm for maximum witnesses, we obtain an algorithm for the relaxed problem that reports for each nonzero entry of the product matrix a witness of rank at most ℓ in time O~((n/ℓ)nω(1,lognℓ,1)). Then, by reducing the relaxed problem to the so called kwitness problem, we provide an algorithm that reports for each nonzero entry C[i, j] of the product matrix C a witness of rank O(⌈ W_{C}(i, j) / k⌉ ), where W_{C}(i, j) is the number of witnesses for C[i, j], with high probability. The algorithm runs in O~ (n^{ω}k^{0.4653}+ n^{2} ^{+} ^{o} ^{(} ^{1} ^{)}k) time, where ω= ω(1, 1, 1 ).
(Less)
 author
 Kowaluk, Mirosław and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2021
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Algorithms and Discrete Applied Mathematics  7th International Conference, CALDAM 2021, Proceedings
 series title
 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 editor
 Mudgal, Apurva and Subramanian, C. R.
 volume
 12601 LNCS
 pages
 12 pages
 publisher
 Springer Science and Business Media B.V.
 conference name
 7th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2021
 conference location
 Rupnagar, India
 conference dates
 20210211  20210213
 external identifiers

 scopus:85101319470
 ISSN
 16113349
 03029743
 ISBN
 9783030678982
 DOI
 10.1007/9783030678999_35
 language
 English
 LU publication?
 yes
 id
 045356265c224a5ab0d75e685b31ae1a
 date added to LUP
 20210310 13:52:42
 date last changed
 20220804 07:49:17
@inproceedings{045356265c224a5ab0d75e685b31ae1a, abstract = {{<p>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 allpairs lowest common ancestor (LCA) problem in directed acyclic graphs (dags). The best known upper timebound on the MW problem for n× n Boolean matrices of the form O(n<sup>2.575</sup>) has not been substantially improved since 2006. In order to obtain faster algorithms for this problem, we study quantum algorithms for MW and approximation algorithms for MW (in the standard computational model). Some of our quantum algorithms are input or output sensitive. Our fastest quantum algorithm for the MW problem, and consequently for the related problems, runs in time O~ (n<sup>2</sup> <sup>+</sup> <sup>λ</sup> <sup>/</sup> <sup>2</sup>) = O~ (n<sup>2.434</sup>), where λ satisfies the equation ω(1,λ,1)=1+1.5λ and ω(1, λ, 1 ) is the exponent of the multiplication of an n× n<sup>λ</sup> matrix by an n<sup>λ</sup>× n matrix. Next, we consider a relaxed version of the MW problem (in the standard model) asking for reporting a witness of bounded rank (the maximum witness has rank 1) for each nonzero entry of the matrix product. First, by adapting the fastest known algorithm for maximum witnesses, we obtain an algorithm for the relaxed problem that reports for each nonzero entry of the product matrix a witness of rank at most ℓ in time O~((n/ℓ)nω(1,lognℓ,1)). Then, by reducing the relaxed problem to the so called kwitness problem, we provide an algorithm that reports for each nonzero entry C[i, j] of the product matrix C a witness of rank O(⌈ W<sub>C</sub>(i, j) / k⌉ ), where W<sub>C</sub>(i, j) is the number of witnesses for C[i, j], with high probability. The algorithm runs in O~ (n<sup>ω</sup>k<sup>0.4653</sup>+ n<sup>2</sup> <sup>+</sup> <sup>o</sup> <sup>(</sup> <sup>1</sup> <sup>)</sup>k) time, where ω= ω(1, 1, 1 ).</p>}}, author = {{Kowaluk, Mirosław and Lingas, Andrzej}}, booktitle = {{Algorithms and Discrete Applied Mathematics  7th International Conference, CALDAM 2021, Proceedings}}, editor = {{Mudgal, Apurva and Subramanian, C. R.}}, isbn = {{9783030678982}}, issn = {{16113349}}, language = {{eng}}, pages = {{440451}}, publisher = {{Springer Science and Business Media B.V.}}, series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}}, title = {{Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products}}, url = {{http://dx.doi.org/10.1007/9783030678999_35}}, doi = {{10.1007/9783030678999_35}}, volume = {{12601 LNCS}}, year = {{2021}}, }