Randomized Communication Complexity
In the above definition, we are concerned with the number of bits that must be deterministically transmitted between two parties. If both the parties are given access to a random number generator, can they determine the value of with much less information exchanged? Yao, in his seminal paper answers this question by defining randomized communication complexity.
A randomized protocol for a function has two-sided error.
A randomized protocol is a deterministic protocol that uses an extra random string in addition to its normal input. There are two models for this: a public string is a random string that is known by both parties beforehand, while a private string is generated by one party and must be communicated to the other party. A theorem presented below shows that any public string protocol can be simulated by a private string protocol that uses O(log n) additional bits compared to the original.
Note that in the probability inequalities above, the outcome of the protocol is understood to depend only on the random string; both strings x and y remain fixed. In other words, if R(x,y) yields g(x,y,r) when using random string r, then g(x,y,r) = f(x,y) for at least half of all choices for the string r.
The randomized complexity is simply defined as the number of bits exchanged in such a protocol.
Note that it is also possible to define a randomized protocol with one-sided error, and the complexity is defined similarly.
Read more about this topic: Communication Complexity
Famous quotes containing the word complexity:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)