# Approximate all-pairs Hamming distances and 0-1 matrix multiplication

Preprint · Miroslaw Kowaluk, Andrzej Lingas, Mia Persson

- Archive id: arxiv:2504.14723
- Published: 2025-04-20
- arXiv: https://arxiv.org/abs/2504.14723
- Source URL: https://arxiv.org/abs/2504.14723
- PDF: https://arxiv.org/pdf/2504.14723
- Provenance: arxiv

## 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. Next, 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. Finally, we provide $(2+ε)$- approximation algorithms for the $\\ell$-center clustering and minimum-diameter $\\ell$-clustering problems in a Hamming space $\\{0,1\\}^d$ that are substantially faster than the known $2$-approximation ones when both $\\ell$ and $d$ are super-logarithmic.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.