Multiplication of 0-1 Matrices via Clustering
(2025) 19th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2025 In Lecture Notes in Computer Science 15828 LNCS. p.92-102- Abstract
We study applications of clustering (in particular the k-center clustering problem) in the design of efficient and practical deterministic algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices A and B with clustered rows or columns, respectively. Let λA and λB denote the minimum maximum radius of a cluster in an ℓ-center clustering of the rows of A and in a k-center clustering of the columns of B, respectively. In particular, when A and B are square matrices of size n×n, we obtain the following results. A simple deterministic algorithm that approximates each entry of the arithmetic matrix product of A and B within an additive error of at most 2λA... (More)
We study applications of clustering (in particular the k-center clustering problem) in the design of efficient and practical deterministic algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices A and B with clustered rows or columns, respectively. Let λA and λB denote the minimum maximum radius of a cluster in an ℓ-center clustering of the rows of A and in a k-center clustering of the columns of B, respectively. In particular, when A and B are square matrices of size n×n, we obtain the following results. A simple deterministic algorithm that approximates each entry of the arithmetic matrix product of A and B within an additive error of at most 2λA in O(n2ℓ) time or at most 2λB in O(n2k) time.A simple deterministic preprocessing of the matrices A and B in O(n2ℓ) time or O(n2k) time after which every query asking for the exact value of an arbitrary entry of the arithmetic matrix product of A and B can be answered in O(λA) time or O(λB) time, respectively.A simple deterministic algorithm for the exact arithmetic matrix product of A and B running in time O(n2(ℓ+k+min{λA,λB})). A simple deterministic algorithm that approximates each entry of the arithmetic matrix product of A and B within an additive error of at most 2λA in O(n2ℓ) time or at most 2λB in O(n2k) time. A simple deterministic preprocessing of the matrices A and B in O(n2ℓ) time or O(n2k) time after which every query asking for the exact value of an arbitrary entry of the arithmetic matrix product of A and B can be answered in O(λA) time or O(λB) time, respectively. A simple deterministic algorithm for the exact arithmetic matrix product of A and B running in time O(n2(ℓ+k+min{λA,λB})).
(Less)
- author
- Jansson, Jesper ; Kowaluk, Mirosław ; Lingas, Andrzej LU and Persson, Mia LU
- organization
- publishing date
- 2025
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- arithmetic matrix multiplication, clustering, Hamming space, minimum spanning tree
- host publication
- Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings
- series title
- Lecture Notes in Computer Science
- editor
- Chau, Vincent ; Dürr, Christoph ; Li, Minming and Lu, Pinyan
- volume
- 15828 LNCS
- pages
- 11 pages
- publisher
- Springer Science and Business Media B.V.
- conference name
- 19th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2025
- conference location
- Paris, France
- conference dates
- 2025-06-30 - 2025-07-02
- external identifiers
-
- scopus:105010825920
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 9789819683116
- DOI
- 10.1007/978-981-96-8312-3_7
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.
- id
- 8ffcf373-3bc2-4dd6-bd9b-5ab803897ce4
- date added to LUP
- 2026-01-13 15:10:41
- date last changed
- 2026-01-27 16:34:28
@inproceedings{8ffcf373-3bc2-4dd6-bd9b-5ab803897ce4,
abstract = {{<p>We study applications of clustering (in particular the k-center clustering problem) in the design of efficient and practical deterministic algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices A and B with clustered rows or columns, respectively. Let λ<sub>A</sub> and λ<sub>B</sub> denote the minimum maximum radius of a cluster in an ℓ-center clustering of the rows of A and in a k-center clustering of the columns of B, respectively. In particular, when A and B are square matrices of size n×n, we obtain the following results. A simple deterministic algorithm that approximates each entry of the arithmetic matrix product of A and B within an additive error of at most 2λ<sub>A</sub> in O(n<sup>2</sup>ℓ) time or at most 2λ<sub>B</sub> in O(n<sup>2</sup>k) time.A simple deterministic preprocessing of the matrices A and B in O(n<sup>2</sup>ℓ) time or O(n<sup>2</sup>k) time after which every query asking for the exact value of an arbitrary entry of the arithmetic matrix product of A and B can be answered in O(λ<sub>A</sub>) time or O(λ<sub>B</sub>) time, respectively.A simple deterministic algorithm for the exact arithmetic matrix product of A and B running in time O(n<sup>2</sup>(ℓ+k+min{λ<sub>A</sub>,λ<sub>B</sub>})). A simple deterministic algorithm that approximates each entry of the arithmetic matrix product of A and B within an additive error of at most 2λ<sub>A</sub> in O(n<sup>2</sup>ℓ) time or at most 2λ<sub>B</sub> in O(n<sup>2</sup>k) time. A simple deterministic preprocessing of the matrices A and B in O(n<sup>2</sup>ℓ) time or O(n<sup>2</sup>k) time after which every query asking for the exact value of an arbitrary entry of the arithmetic matrix product of A and B can be answered in O(λ<sub>A</sub>) time or O(λ<sub>B</sub>) time, respectively. A simple deterministic algorithm for the exact arithmetic matrix product of A and B running in time O(n<sup>2</sup>(ℓ+k+min{λ<sub>A</sub>,λ<sub>B</sub>})).</p>}},
author = {{Jansson, Jesper and Kowaluk, Mirosław and Lingas, Andrzej and Persson, Mia}},
booktitle = {{Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings}},
editor = {{Chau, Vincent and Dürr, Christoph and Li, Minming and Lu, Pinyan}},
isbn = {{9789819683116}},
issn = {{1611-3349}},
keywords = {{arithmetic matrix multiplication; clustering; Hamming space; minimum spanning tree}},
language = {{eng}},
pages = {{92--102}},
publisher = {{Springer Science and Business Media B.V.}},
series = {{Lecture Notes in Computer Science}},
title = {{Multiplication of 0-1 Matrices via Clustering}},
url = {{http://dx.doi.org/10.1007/978-981-96-8312-3_7}},
doi = {{10.1007/978-981-96-8312-3_7}},
volume = {{15828 LNCS}},
year = {{2025}},
}