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)