New answers tagged lower-bounds
2
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
