Newman's Theorem

In the literature of communication complexity, two models of random protocols are used - common random string model and private random string model. In a common random string model, Alice and Bob have access to a common random string which they use in their calculation. On the contrary, in private random string model, Alice or Bob cannot have access to other person's private random string.

It is trivial to see that common random string model subsumes private random string model as any private coin protocol can be simulated by a public coin protocol where the common random string is nothing but concatenation of the private random strings of Alice and Bob. The interest question to ask is whether the opposite direction is possible.

We investigate the relative power of these models and show that the two models are essentially equal.