1
$\begingroup$

I recently started learning about distributed computation on graphs (not to be confused with parallel computation with threads).

I have seen as a side note in a few lower bound proofs, a reference that says the proof could be shorter using the "linear lower bound theorem for the Equality problem", but I couldn't find the statement or proof of this theorem.

I would like to know a few things:

  • What exactly is this "Equality" problem? (how is it formulated?)
  • Where can I find a proof for its lower bound? (or if the proof is short enough, I would be glad if you could add it here)

Thanks!

$\endgroup$
3
$\begingroup$

This is probably referring to the communication complexity of the function $f(x,y) = 1$ if $x=y$ and $f(x,y) = 0$ if $x \ne y$. See https://en.wikipedia.org/wiki/Communication_complexity#Example:_%7F'%22%60UNIQ--postMath-00000031-QINU%60%22'%7F for the formulation and a proof of the lower bound.

$\endgroup$
3
  • $\begingroup$ Thanks! Is there a theorem connecting the communication complexity of some $f$, to the complexity of a two-node graph distributed computation of the same problem? $\endgroup$ – nir shahar Feb 4 at 10:01
  • 2
    $\begingroup$ You can formulate and prove this theorem yourself. The idea is that a protocol in the distributed setting can be converted to a protocol in the communication complexity setting. $\endgroup$ – Yuval Filmus Feb 4 at 19:42
  • $\begingroup$ The other direction is obvious. I will try to prove this alone, thanks! $\endgroup$ – nir shahar Feb 4 at 21:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.