# “Equality” problem in distributed computation

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!

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.
• 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? – nir shahar Feb 4 at 10:01