Sign-Rank of $k$-Hamming Distance is Constant

Mika Göös, Nathaniel Harms, Valentin Imbach +1

We prove that the sign-rank of the $k$-Hamming Distance matrix on $n$ bits is $2^{O(k)}$, independent of the number of bits $n$. This strongly refutes the conjecture of Hatami, Hat…