Abstract -The communication complexity of a two-variable function f ( x , y ) is the number of information bits two communicators need to exchange to compute f when, initially, each knows only one of the variables. There are several communication-complexity measures corresponding to whether 1) the worst case or average number of bits is considered, 2) computation errors are allowed or not, and 3) randomization is allowed or not. Tight bounds are provided for the typical behavior of all bounded-error communication-complexity measures of Boolean functions. Let 3 bethesetoffunctionsf: { 0 ;~~, n -l ) X { 0 ;~~, n -l } -t { O , l ) that contain s ones (i.e., I{(x, v ) : f(x, y) =1}1 =s). It is shown that for every n I s I t i 2 / 2 , the communication-complexity measures fall into two classes: logpi cluss -the error-free worst case randomized complexity and, more importantly, the error-free worst case deterministic complexity of most functions in 3 are between log n -4 and log n + 1 bits (this holds even f o r s = n ) ; /og(s/n) cluss-the c-error worst case randomized complexity and the c-error average randomized complexity of most functions in e are between (1 -2c)(log (s/ n ) -2 log log ( s / n ) and (1 -2c)(log(s/n) + 5.3 loglog n) bits. More importantly, the error-free average deterministic complexity of all functions in is less than log(s/n)+8.3loglogn bits. For most of these functions it is also t log(s/n) -2loglog(s/n) bits. The difference between the complexities of the log n class and the l o g ( s / n ) class ranges from a constant (for s = n2/2) to exponential (for s --n log n ) . In particular, since most functions have about n2/2 ones, all their complexity measures are around log n bits. OMMUNICATION complexity was first introduced C by Abelson [l] and Yao [2]. It is concerned with different aspects of the following problem: n is a positive integer, f is a binary function defined on (0,. . -, n -1 ) X (0; . -, n -l } , and c 2 0. Two communicators, P, having a random integer X E (0;. ., n -1} and P, having a random integer Y E (0; . . , n -l}, use a predetermined protocol to compute f( X , Y ) with probability of error I c. How many bits must they exchange on the average? at worst? The next two sections make these notions more precise: in Section I1 we formally define the deterministic model; in Section I11 we describe randomized protocols and compare them to deterministic ones. In Section IV we survey previous work and describe the results obtained in this paper. These results are proved in Section V. Communication is performed over a binary channel that can carry only one bit at a time. Therefore, each communicator, in turn, transmits a (possible empty) sequence of bits that we call a string or a message. Since empty messages are allowed, we lose no generality by assuming that Px transmits the first message. Communication proceeds according to a predetermined protocol that, at each time, specifies the message transmitted and, at the end of the communication, decides on the computed value that the communicators (P, and P,) assume is the correct value of the function. The protocol is deterministic if, whenever P, and P, have the same pair of random integers, they transmit the same sequence of messages and decide on the same computed value. With this communication model in mind, we formally define deterministic protocols. The definition is similar to that of [3] and [4]. It differs from that of [3] in that 1) it views the protocol as a codebook (an approach that facilitates information-theoretic treatment), and 2) the computed value of the function does not have to be transmitted explicitly. An input is an ordered pair O ,~~~, n -l }~{ O ,~~~, n -l } can therefore be defined as a mapping that associates with each input.
The average and randomized complexity of Boolean functions are studied in REF .
Average and Randomized Communication Complexity
IEEE Trans. Inf. Theory
IEEE Trans. Inf. Theory
Computer Science