All Questions
Tagged with communication-complexity sets
2 questions
4
votes
1
answer
98
views
Compute the union of two sets between two endpoints minimizing communication complexity
I have two endpoints, $a$ and $b$, that can communicate through a channel. $a$ is storing a set of fixed-length strings $A = \{a_1, \ldots, a_{N_A}\}$, and $b$ is storing another set of fixed-length ...
- 205
4
votes
1
answer
115
views
Communication complexity of comparing sets, for Bitcoin
In Bitcoin, when one node wants to tell another node about a block, it sends the block header, then all the transactions it contains. This is inefficient, because the receiving node might already have ...
- 143