Given two subsets of the $d$-dimensional hypercube (i.e., $M, N \subseteq \{0,1\}^d$), I am looking for an algorithm which retrieves the points $m\in M, n\in N$ s.t. the hamming distance (or $L_1$-distance on the hypercube) $d_H(m,n)$ is minimal. The naive algorithm which checks just each pair needs $|M|\cdot |N| \cdot d$ time, is there any better result known?For simplicity we may assume that $|M|=|N|=d$.
Finding the closest pair between two sets of points on the hypercube
cg.comp geom
Just realized that you are asking for the case that $|M|=|N|=d$. Then you can do matrix multiplication, right? Write $M$ is a row matrix $X$, $N$ as a column matrix $Y$, negate the entries of $Y$, and compute the matrix $Z=XY$. Clearly, the $z_{i,j}$ is the Hamming distance between the $i$th point of $M$ and the $j$th point of $N$. According to the last breakthroughs this has running time $O(d^{2.3727})$ (but I have a 50,000 pages manuscript that shows how to do this matrix multiplication in $O(d^{2.3726999999})$ time by a really simple algorithm).You can get similar effect if the matrices are not squares. I think Uri Zwick has a paper about fast matrix multiplication in this case.In some sense, this is not too interesting - we want to avoid the $O(|M| * |N|)$  term. The improvements in the $d$ term are kind of meh, meh...