|
Abstract : |
In the two-player communication model introduced by Yao [Y79], Alice and Bob wish to collaboratively evaluate a function f(x; y) in which Alice knows only input x and Bob knows only input y. Both players have unlimited computational power. The objective is to minimize the amount of communication. Yao [Y79] also introduced an oblivious version of this communication game which we call the simultaneous messages (SM) model. The difference is that in the SM model, Alice and Bob don't communicate with each other. Instead, they simultaneously send a message to a referee, who sees none of the inputs. The referee then announces the function value. The deterministic two-player SM complexity of any function is straightforward to determine. Yao suggested the randomized version of this model, where each player has access to private coin flips. Our main result is that the order of magnitude of the randomized SM complexity of any function f is at least the square root of the deterministic SM complexity of f. We found this result independently but subsequently to I. Newman and M. Szegedy [NS] who obtain this lower bound for the "equality " function. Our proof is also of interest for its simplicity; a proof in a similar spirit was also found by J. Bourgain and A. Wigderson. We also show that the quadratic reduction actually does occur for the "equality " function. This, combined with our main result, settles Yao's question [Y79], asking the exact randomized SM complexity of this function. We note that the use of O(log n) public coins reduces the complexity of "equality " to constant. 1, |
