TY - JOUR
T1 - Faster multi-witnesses for Boolean matrix multiplication
AU - Gasieniec, Leszek
AU - Kowaluk, Mirosław
AU - Lingas, Andrzej
N1 - Funding Information:
E-mail addresses: L.A.Gasieniec@liverpool.ac.uk (L. Gąsieniec), kowaluk@mimuw.edu.pl (M. Kowaluk), Andrzej.Lingas@cs.lth.se (A. Lingas). 1 Research supported in part by the Royal Society International Joint Project, IJP – 2006/R2. 2 Research supported by the grant of the Polish Ministry of Science and Higher Education N20600432/0806. 3 Research supported in part by VR grant 621-2005-4806.
PY - 2009/1/31
Y1 - 2009/1/31
N2 - A generalization of the the k-witness problem of computing a single witness in a Boolean matrix multiplication, where k witnesses are determined for each positive entry of the Boolean product, is studied. It is also shown that k-witness problem can be deterministically solved in certain a time by an algorithm based on rectangular matrix multiplication. The bounded k-witness problem is a variant of the bounded k-reconstruction problem, in which all witnesses are recovered for entries that have at most k witnesses. The results also shows that The k-witness problem for the Boolean product of two n dimensional matrices can be deterministically solved in a certain time, by the algorithm using rectangular matrix multiplication. It is also found that the randomized algorithm for the k-witness problem matches the lower bound at the two extremes of the matrix.
AB - A generalization of the the k-witness problem of computing a single witness in a Boolean matrix multiplication, where k witnesses are determined for each positive entry of the Boolean product, is studied. It is also shown that k-witness problem can be deterministically solved in certain a time by an algorithm based on rectangular matrix multiplication. The bounded k-witness problem is a variant of the bounded k-reconstruction problem, in which all witnesses are recovered for entries that have at most k witnesses. The results also shows that The k-witness problem for the Boolean product of two n dimensional matrices can be deterministically solved in a certain time, by the algorithm using rectangular matrix multiplication. It is also found that the randomized algorithm for the k-witness problem matches the lower bound at the two extremes of the matrix.
KW - Algorithms
KW - Analysis of algorithms
KW - Boolean matrix multiplication
KW - Combinatorial problems
KW - Lowest common ancestors in dags
KW - Time complexity, directed acyclic graph (dag)
KW - Witnesses for Boolean matrix product
UR - http://www.scopus.com/inward/record.url?scp=59149098020&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=59149098020&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2008.10.012
DO - 10.1016/j.ipl.2008.10.012
M3 - Article
AN - SCOPUS:59149098020
SN - 0020-0190
VL - 109
SP - 242
EP - 247
JO - Information Processing Letters
JF - Information Processing Letters
IS - 4
ER -