Multiplication of 0-1 Matrices via Clustering
(2026) In Theory of Computing Systems 70(3).- Abstract
We study applications of clustering (in particular, the Hamming k-center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). We provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an ℓ-center clustering of the rows of the first matrix or an k-center clustering of the columns of the second... (More)
We study applications of clustering (in particular, the Hamming k-center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). We provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an ℓ-center clustering of the rows of the first matrix or an k-center clustering of the columns of the second matrix. We use the approximation algorithm as a preprocessing after which a query asking for the exact value of an arbitrary entry in the product matrix can be answered in time proportional to the additive error. As a consequence, we obtain a simple deterministic algorithm for the exact matrix product of 0-1 matrices. We also present an alternative simple deterministic algorithm for the exact product and in addition, faster analogous randomized algorithms for an approximate and the exact matrix products of 0-1 matrices based on randomized ℓ- and k-center clustering.
(Less)
- author
- Jansson, Jesper LU ; Kowaluk, Miroslaw ; Lingas, Andrzej LU and Persson, Mia LU
- organization
- publishing date
- 2026-09
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Arithmetic matrix multiplication, Hamming space, k-center clustering
- in
- Theory of Computing Systems
- volume
- 70
- issue
- 3
- article number
- 41
- publisher
- Springer
- external identifiers
-
- scopus:105043470666
- ISSN
- 1432-4350
- DOI
- 10.1007/s00224-026-10286-7
- language
- English
- LU publication?
- yes
- id
- 58e66118-e323-43e8-b612-66be3f89c9a3
- date added to LUP
- 2026-09-28 16:01:54
- date last changed
- 2026-09-28 16:02:54
@article{58e66118-e323-43e8-b612-66be3f89c9a3,
abstract = {{<p>We study applications of clustering (in particular, the Hamming k-center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). We provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an ℓ-center clustering of the rows of the first matrix or an k-center clustering of the columns of the second matrix. We use the approximation algorithm as a preprocessing after which a query asking for the exact value of an arbitrary entry in the product matrix can be answered in time proportional to the additive error. As a consequence, we obtain a simple deterministic algorithm for the exact matrix product of 0-1 matrices. We also present an alternative simple deterministic algorithm for the exact product and in addition, faster analogous randomized algorithms for an approximate and the exact matrix products of 0-1 matrices based on randomized ℓ- and k-center clustering.</p>}},
author = {{Jansson, Jesper and Kowaluk, Miroslaw and Lingas, Andrzej and Persson, Mia}},
issn = {{1432-4350}},
keywords = {{Arithmetic matrix multiplication; Hamming space; k-center clustering}},
language = {{eng}},
number = {{3}},
publisher = {{Springer}},
series = {{Theory of Computing Systems}},
title = {{Multiplication of 0-1 Matrices via Clustering}},
url = {{http://dx.doi.org/10.1007/s00224-026-10286-7}},
doi = {{10.1007/s00224-026-10286-7}},
volume = {{70}},
year = {{2026}},
}