A Faster Algorithm for Finding Closest Pairs in Hamming Metric

Andre Esser, Robert Kübler, Floyd Zweydinger

We study the Closest Pair Problem in Hamming metric, which asks to find the pair with the smallest Hamming distance in a collection of binary vectors. We give a new randomized algo…