No title
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
