Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products
(2023) In International Journal of Foundations of Computer Science- 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 classical 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 Õ(n2+λ/2)... (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 classical 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 Õ(n2+λ/2) = Õ(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 classical 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 Õ((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 Õ(nωk0.4653 + n2+o(1)k) time, where ω = ω(1, 1, 1).
(Less)
- author
- Kowaluk, Mirosław and Lingas, Andrzej LU
- organization
- publishing date
- 2023-11-10
- type
- Contribution to journal
- publication status
- epub
- subject
- keywords
- approximation algorithms, maximum witnesses, quantum algorithms, Witnesses of Boolean matrix product
- in
- International Journal of Foundations of Computer Science
- publisher
- World Scientific Publishing
- external identifiers
-
- scopus:85177068740
- ISSN
- 0129-0541
- DOI
- 10.1142/S0129054123500259
- language
- English
- LU publication?
- yes
- additional info
- :
- id
- 1c545b5d-8f9f-4a37-bc3c-4d8c48b7cb45
- date added to LUP
- 2024-01-08 15:50:32
- date last changed
- 2024-03-06 13:01:40
@article{1c545b5d-8f9f-4a37-bc3c-4d8c48b7cb45,
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(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 classical 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 Õ(n2+λ/2) = Õ(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 classical 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 Õ((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 Õ(nωk0.4653 + n2+o(1)k) time, where ω = ω(1, 1, 1).</p>}},
author = {{Kowaluk, Mirosław and Lingas, Andrzej}},
issn = {{0129-0541}},
keywords = {{approximation algorithms; maximum witnesses; quantum algorithms; Witnesses of Boolean matrix product}},
language = {{eng}},
month = {{11}},
publisher = {{World Scientific Publishing}},
series = {{International Journal of Foundations of Computer Science}},
title = {{Quantum and Approximation Algorithms for Maximum Witnesses of Boolean Matrix Products}},
url = {{http://dx.doi.org/10.1142/S0129054123500259}},
doi = {{10.1142/S0129054123500259}},
year = {{2023}},
}