An improved bound on Boolean matrix multiplication for highly clustered data
(2003) 8th International Workshop, WADS 2003 In Lecture Notes in Computer Science 2748. p.329339 Abstract
 We consider the problem of computing the product of two n x n Boolean matrices A and B. For two 0  I strings s = s(1)s(2) .... s(m) and u = u(1)u(2) ... u(m), an extended Hamming distance, eh(s, u), between the strings, is defined by a recursive equation eh(s, u) = eh(s(l+1) ... s(m), u(l+1) ... u(m)) + (s(1) + u(1) mod 2), where l is the maximum number, s.t., s(j) = s, and u(j) = u(1) for j = For any n x n Boolean matrix C, let GC be a complete weighted graph on the rows of C, where the weight of an edge between two rows is equal to its extended Hamming distance. Next, let MWT(C) be the weight of a minimum weight spanning, tree of GC. WE! show that the product of A and B as well as the so called witnesses of the product can be computed... (More)
 We consider the problem of computing the product of two n x n Boolean matrices A and B. For two 0  I strings s = s(1)s(2) .... s(m) and u = u(1)u(2) ... u(m), an extended Hamming distance, eh(s, u), between the strings, is defined by a recursive equation eh(s, u) = eh(s(l+1) ... s(m), u(l+1) ... u(m)) + (s(1) + u(1) mod 2), where l is the maximum number, s.t., s(j) = s, and u(j) = u(1) for j = For any n x n Boolean matrix C, let GC be a complete weighted graph on the rows of C, where the weight of an edge between two rows is equal to its extended Hamming distance. Next, let MWT(C) be the weight of a minimum weight spanning, tree of GC. WE! show that the product of A and B as well as the so called witnesses of the product can be computed in time (O) over bar (n(n + min{MWT(A), MWT(Bt)}))(1). Since the extended Hamming distance between two strings never exceeds the standard Hamming distance between them, our result subsumes an earlier similar result on the Boolean matrix product in terms of the Hamming distance due to Bjorklund and Lingas [4]. We also observe that min{MWT(A),MWT(Bt)} = O(min{r(A),r(B)}), where r(A) and r(B) reflect the minimum number of rectangles required to cover ls in A and B, respectively. Hence, our result also generalizes the recent upper bound on the Boolean matrix product in terms of r(A) and r(B), due to Lingas [12]. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/299947
 author
 Gasieniec, L and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2003
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Algorithms and Data Structures
 series title
 Lecture Notes in Computer Science
 volume
 2748
 pages
 329  339
 publisher
 Springer
 conference name
 8th International Workshop, WADS 2003
 conference location
 Ottawa, Ontario, Canada
 conference dates
 20030730  20030801
 external identifiers

 wos:000185605300029
 scopus:35248863004
 ISSN
 03029743
 16113349
 ISBN
 9783540405450
 DOI
 10.1007/9783540450788_29
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 fb5e93c32e7c4641b5af514ef4020281 (old id 299947)
 date added to LUP
 20160401 12:32:56
 date last changed
 20210630 05:36:15
@inproceedings{fb5e93c32e7c4641b5af514ef4020281, abstract = {We consider the problem of computing the product of two n x n Boolean matrices A and B. For two 0  I strings s = s(1)s(2) .... s(m) and u = u(1)u(2) ... u(m), an extended Hamming distance, eh(s, u), between the strings, is defined by a recursive equation eh(s, u) = eh(s(l+1) ... s(m), u(l+1) ... u(m)) + (s(1) + u(1) mod 2), where l is the maximum number, s.t., s(j) = s, and u(j) = u(1) for j = For any n x n Boolean matrix C, let GC be a complete weighted graph on the rows of C, where the weight of an edge between two rows is equal to its extended Hamming distance. Next, let MWT(C) be the weight of a minimum weight spanning, tree of GC. WE! show that the product of A and B as well as the so called witnesses of the product can be computed in time (O) over bar (n(n + min{MWT(A), MWT(Bt)}))(1). Since the extended Hamming distance between two strings never exceeds the standard Hamming distance between them, our result subsumes an earlier similar result on the Boolean matrix product in terms of the Hamming distance due to Bjorklund and Lingas [4]. We also observe that min{MWT(A),MWT(Bt)} = O(min{r(A),r(B)}), where r(A) and r(B) reflect the minimum number of rectangles required to cover ls in A and B, respectively. Hence, our result also generalizes the recent upper bound on the Boolean matrix product in terms of r(A) and r(B), due to Lingas [12].}, author = {Gasieniec, L and Lingas, Andrzej}, booktitle = {Algorithms and Data Structures}, isbn = {9783540405450}, issn = {03029743}, language = {eng}, pages = {329339}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {An improved bound on Boolean matrix multiplication for highly clustered data}, url = {http://dx.doi.org/10.1007/9783540450788_29}, doi = {10.1007/9783540450788_29}, volume = {2748}, year = {2003}, }