4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ A slightly better upper bound is $\log \binom{n}{k}$. $\endgroup$
    – András Salamon
    Jun 8, 2016 at 14:49

0

Reset to default

Your Answer

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