A new coding-based algorithm for finding closest pair of vectors

Abstract Given n vectors x 0 , x 1 , … , x n − 1 in { 0 , 1 } m , how to find two vectors whose pairwise Hamming distance is minimum? This problem is known as the Closest Pair Problem . If these vectors are generated uniformly at random except two of them are correlated with Pearson-correlation coefficient ρ , then the problem is called the Light Bulb Problem . In this work, we propose a novel coding-based scheme for the Closest Pair Problem. We design both randomized and deterministic algorithms, which achieve the best-known running time when the length of input vectors m is small and the minimum distance is very small compared to m . Specifically, the running time of our randomized algorithm is O ( n log 2 ⁡ n ⋅ 2 c m ⋅ poly ( m ) ) and the running time of our deterministic algorithm is O ( n log ⁡ n ⋅ 2 c ′ m ⋅ poly ( m ) ) , where c and c ′ are constants depending only on the (relative) distance of the closest pair. When applied to the Light Bulb Problem, our result yields state-of-the-art deterministic running time when the Pearson-correlation coefficient ρ is very large. Specifically, when ρ ≥ 0.9933 , our deterministic algorithm runs faster than the previously best deterministic algorithm (Alman, SOSA 2019).