Some complexity questions related to distributive computing(Preliminary Report)

TLDR

The study examines distributed evaluation of a Boolean function f on inputs held separately by two parties, each knowing only its own index from sets M and N. The authors aim to analyze the communication complexity of computing f(i, j) cooperatively between two parties. They model the interaction as alternating one‑bit exchanges and define the communication cost as the minimal number of bits required by any algorithm. For the example f(i, j) = (i + j) mod 2, a single bit from P1 suffices, establishing the optimality of one‑bit communication.

Abstract

Let M = {0, 1, 2, ..., m—1} , N = {0, 1, 2,..., n—1} , and f:M × N → {0, 1} a Boolean-valued function. We will be interested in the following problem and its related questions. Let i ε M, j ε N be integers known only to two persons P1 and P2, respectively. For P1 and P2 to determine cooperatively the value f(i, j), they send information to each other alternately, one bit at a time, according to some algorithm. The quantity of interest, which measures the information exchange necessary for computing f, is the minimum number of bits exchanged in any algorithm. For example, if f(i, j) = (i + j) mod 2. then 1 bit of information (conveying whether i is odd) sent from P1 to P2 will enable P2 to determine f(i, j), and this is clearly the best possible.