Two-Party Function Computation on the Reconciled Data


Assume a distributed system with two users, each user possesses a collection of binary strings. We introduce a new problem termed function computation on the reconciled data, which generalizes a set reconciliation problem in the literature. It is shown that any deterministic protocol that computes a sum and a product of reconciled sets of non-negative integers has to communicate at least $2^n + n - 1$ and $2^n + n - 3$ bits in the worst-case scenario, respectively, where $n$ is the length of the binary string representations of the numbers. Connections to other problems in computer science, such as set disjointness and finding the intersection, are established, yielding a variety of additional bounds on the communication complexity. A protocol, which is based on use of a family of hash functions is presented, and its characteristics are analyzed.

ANTA Seminar
Aalto University, Finland