@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}},
}