Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products

Kowaluk, Mirosław and Lingas, Andrzej LU (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.440-451
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 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 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 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 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~ (n2 + λ / 2) = O~ (n2.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 non-zero 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 non-zero 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 k-witness problem, we provide an algorithm that reports for each non-zero entry C[i, j] of the product matrix C a witness of rank O(⌈ WC(i, j) / k⌉ ), where WC(i, j) is the number of witnesses for C[i, j], with high probability. The algorithm runs in O~ (nωk0.4653+ n2 + o ( 1 )k) time, where ω= ω(1, 1, 1 ).

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
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
2021-02-11 - 2021-02-13
external identifiers
  • scopus:85101319470
ISSN
1611-3349
0302-9743
ISBN
9783030678982
DOI
10.1007/978-3-030-67899-9_35
language
English
LU publication?
yes
id
04535626-5c22-4a5a-b0d7-5e685b31ae1a
date added to LUP
2021-03-10 13:52:42
date last changed
2022-08-04 07:49:17
@inproceedings{04535626-5c22-4a5a-b0d7-5e685b31ae1a,
  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 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(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 non-zero 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 non-zero 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 k-witness problem, we provide an algorithm that reports for each non-zero 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         = {{1611-3349}},
  language     = {{eng}},
  pages        = {{440--451}},
  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/978-3-030-67899-9_35}},
  doi          = {{10.1007/978-3-030-67899-9_35}},
  volume       = {{12601 LNCS}},
  year         = {{2021}},
}