It is something that I think should be known: what is nondeterministic communication complexity of following task:

is $H(x,y) \geq k$?

There is an obvious upper bound $k \log(n)$. I would expect this to be tight up to a $o(\log(n))$ additive term (for small $k$). Is this known?

  • 2
    $\begingroup$ A slightly better upper bound is $\log \binom{n}{k}$. $\endgroup$ Jun 8, 2016 at 14:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.