Randomized simultaneous messages: solution of a problem of Yao in communication complexity

We solve a 17 year old problem of A.C.C. Yao (1979). In the two-player communication model introduced by Yao in 1979, 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 (1979) 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 messages to a referee, who sees none of the input. The referee then announces the function value. The deterministic two-player SM complexity of any function is straight forward 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 in February 1996, independently but subsequently to I. Newman and M. Szegedy (1996) who obtained this lower bound for the special case of the “equality” function. Our proof is entirely different from and considerably simpler than the Newman-Szegedy solution. A proof similar in spirit to ours, was found by J. Bourgain and A. Wigderson simultaneously to us (unpublished); we include an outline of their proof. The quadratic reduction actually does occur for the “equality” function. We give a new proof of this fact. This result, combined with our main result, settles Yao´s question, asking the exact randomized SM complexity of the equality function. The lower bound proof uses the probabilistic method; the upper bound uses linear algebra. We also give a constructive proof that O(log n) public coins reduce the complexity of “equality” to constant