Information-theoretic bounds for cooperative computation


We consider functions with sets of binary vectors of length $n$ as domains. Given a function $f$, the protocol $F$ computing $f$ is a function outputting a set of message vectors $M_1, ..., M_r$ such that for any input sets $S_A$ and $S_B$ the value of the last message vector $M_r$ equals to the value of the function on the union of the sets, i.e. $M_r = f(S_A \cup S_B)$. The cooperative two-party function computation problem is the problem of finding a protocol $F$ which minimizes the communication complexity $\sum_{i=1}^r |M_i|$. We give lower bounds on the communication complexity of protocols computing certain functions.

Estonian-Latvian Theory Days
Ratnieki, Latvia