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$ – András Salamon Jun 8 '16 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.