New answers tagged


When $\epsilon < 1/2$, you can pick a code with exponentially many codewords and minimum distance $\epsilon n$. If the inputs are promised to be in the code, your problem becomes EQUALITY, and so requires $\Omega(n)$ communication. When $\epsilon = 1$, the problem becomes easy (send the first bit).

Top 50 recent answers are included