Title: Two-Party Function Computation on the Reconciled Data,
Abstract: In this paper, we initiate a study of a new problem termed function
computation on the reconciled data, which generalizes a set reconciliation
problem in the literature. Assume a distributed data storage system with two
users $A$ and $B$. The users possess a collection of binary vectors $S_{A}$ and
$S_{B}$, respectively. They are interested in computing a function $\phi$ of
the reconciled data $S_{A} \cup S_{B}$.
It is shown that any deterministic protocol, which computes a sum and a
product of reconciled sets of binary vectors represented as nonnegative
integers, has to communicate at least $2^n + n - 1$ and $2^n + n - 2$ bits in
the worst-case scenario, respectively, where $n$ is the length of the binary
vectors. Connections to other problems in computer science, such as set
disjointness and finding the intersection, are established, yielding a variety
of additional upper and lower bounds on the communication complexity. A
protocol for computation of a sum function, which is based on use of a family
of hash functions, is presented, and its characteristics are analyzed.