3 - Randomization

Summary

In the basic model of communication complexity, Alice and Bob were all powerful, but deterministic. This means that in any stage, when one of the players needs to communicate a bit, the value of this bit is a deterministic function of the player's input and the communication so far. In this chapter, we study what happens when Alice and Bob are allowed to act in a randomized fashion. That is, the players are also allowed to “toss coins” during the execution of the protocol and take into account the outcome of the coin tosses when deciding what messages to send. This implies that the communication on a given input (x, y) is not fixed anymore but instead it becomes a random variable. Similarly, the output computed by a randomized protocol on input (x, y) is also a random variable. As a result, the success of a randomized protocol can be defined in several ways. The first possibility, which is more conservative (sometimes called Las-Vegas protocols), is to consider only protocols that always output the correct value f (x, y). The more liberal possibility is to allow protocols that may err, but for every input (x, y) are guaranteed to compute the correct value f(x, y) with high probability (sometimes called Monte-Carlo protocols). Similarly, the cost of a randomized protocol can also be defined in several ways. We can either analyze the worst case behavior of the protocol, or we can analyze the average case behavior.