# Testing Equality in Networks

Yesterday, I went to an interesting talk by Klim Efremenko about testing equality in networks. The talk was based on his joint paper with Noga Alon and Benny Sudakov. The basic problem is as follows. Suppose there is a network with $$k$$ nodes, and each node $$v$$ has an input in the form of an $$n$$-bit string $$M_v \in \{0, 1\}^n$$. All of the nodes in the network want to verify that all of their strings are equal, i.e., that $$M_v = M_u$$ for all…

Suppose two players, Alice and Bob, each hold equal sized subsets of $$[n] = {1, 2, \ldots, n}$$. A third party, Carole, wishes to convince Alice and Bob that their subsets are disjoint, i.e., their sets have no elements in common. How efficiently can Carole prove to Alice and Bob that their sets are disjoint? To formalize the situation, suppose $$k$$ is an integer with $$1 \leq k \leq n$$, and let $$A$$ and $$B$$ be, respectively, Alice and Bob's subsets of $$[n]$$, both of size $$k$$. Carole produces a…