Approximate All-Pairs Hamming Distances and 0–1 Matrix Multiplication
(2026) 3rd International Conference on Applied Algorithms, ICAA 2026 In Lecture Notes in Computer Science 16423 LNCS. p.38-49- Abstract
Arslan showed that computing all-pairs Hamming distances is easily reducible to arithmetic 0–1 matrix multiplication (IPL 2018). We provide a reverse, linear-time reduction of arithmetic 0–1 matrix multiplication to computing all-pairs distances in a Hamming space. On the other hand, we present a fast randomized algorithm for approximate all-pairs distances in a Hamming space. By combining it with our reduction, we obtain also a fast randomized algorithm for approximate 0–1 matrix multiplication. Finally, we present an output-sensitive randomized algorithm for a minimum spanning tree of a set of points in a generalized Hamming space, the lower is the cost of the minimum spanning tree the faster is our algorithm.(A preliminary version of... (More)
Arslan showed that computing all-pairs Hamming distances is easily reducible to arithmetic 0–1 matrix multiplication (IPL 2018). We provide a reverse, linear-time reduction of arithmetic 0–1 matrix multiplication to computing all-pairs distances in a Hamming space. On the other hand, we present a fast randomized algorithm for approximate all-pairs distances in a Hamming space. By combining it with our reduction, we obtain also a fast randomized algorithm for approximate 0–1 matrix multiplication. Finally, we present an output-sensitive randomized algorithm for a minimum spanning tree of a set of points in a generalized Hamming space, the lower is the cost of the minimum spanning tree the faster is our algorithm.(A preliminary version of this article appeared in arXiv.org.)
(Less)
- author
- Kowaluk, Mirosław ; Lingas, Andrzej LU and Persson, Mia LU
- organization
- publishing date
- 2026
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- approximation algorithm, arithmetic matrix multiplication, Hamming distance, Hamming space, minimum spanning tree
- host publication
- Applied Algorithms - Third International Conference, ICAA 2026, Proceedings
- series title
- Lecture Notes in Computer Science
- editor
- Zaroliagis, Christos ; Bhandari, Dinabandhu ; Gupta, Prosenjit and Das, Swagatam
- volume
- 16423 LNCS
- pages
- 12 pages
- publisher
- Springer Science and Business Media B.V.
- conference name
- 3rd International Conference on Applied Algorithms, ICAA 2026
- conference location
- Kolkata, India
- conference dates
- 2026-01-07 - 2026-01-09
- external identifiers
-
- scopus:105028361115
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 9783032156204
- DOI
- 10.1007/978-3-032-15621-1_4
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
- id
- c359563c-b9d8-4a8f-ba00-7eb164aa004d
- date added to LUP
- 2026-02-25 10:07:40
- date last changed
- 2026-05-20 23:18:26
@inproceedings{c359563c-b9d8-4a8f-ba00-7eb164aa004d,
abstract = {{<p>Arslan showed that computing all-pairs Hamming distances is easily reducible to arithmetic 0–1 matrix multiplication (IPL 2018). We provide a reverse, linear-time reduction of arithmetic 0–1 matrix multiplication to computing all-pairs distances in a Hamming space. On the other hand, we present a fast randomized algorithm for approximate all-pairs distances in a Hamming space. By combining it with our reduction, we obtain also a fast randomized algorithm for approximate 0–1 matrix multiplication. Finally, we present an output-sensitive randomized algorithm for a minimum spanning tree of a set of points in a generalized Hamming space, the lower is the cost of the minimum spanning tree the faster is our algorithm.(A preliminary version of this article appeared in arXiv.org.)</p>}},
author = {{Kowaluk, Mirosław and Lingas, Andrzej and Persson, Mia}},
booktitle = {{Applied Algorithms - Third International Conference, ICAA 2026, Proceedings}},
editor = {{Zaroliagis, Christos and Bhandari, Dinabandhu and Gupta, Prosenjit and Das, Swagatam}},
isbn = {{9783032156204}},
issn = {{1611-3349}},
keywords = {{approximation algorithm; arithmetic matrix multiplication; Hamming distance; Hamming space; minimum spanning tree}},
language = {{eng}},
pages = {{38--49}},
publisher = {{Springer Science and Business Media B.V.}},
series = {{Lecture Notes in Computer Science}},
title = {{Approximate All-Pairs Hamming Distances and 0–1 Matrix Multiplication}},
url = {{http://dx.doi.org/10.1007/978-3-032-15621-1_4}},
doi = {{10.1007/978-3-032-15621-1_4}},
volume = {{16423 LNCS}},
year = {{2026}},
}