Some complexity questions related to distributive computing(Preliminary Report)

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.