14 - Further Topics

Summary

In this chapter, we briefly mention several relevant topics not covered in this book.

Noisy Channels

[Schulman 1992, Schulman 1993] present a variant of the two-party model, in which Alice and Bob are communicating using a noisy channel. That is, each bit that is sent by either Alice of Bob is flipped with some probability λ < 1/2 (which is independent from what happens in other transmissions). Say, a player may send the bit 0 but the other player will receive 1. The question is what is the communication complexity of computing a function f in such a model.

Note that if Alice and Bob use a protocol P that was designed for the standard (noiseless) model, each such flip may lead the two players to be in different places in the protocol tree, and hence all subsequent communication may be meaningless. A naive approach would be to send each bit ℓ times instead of only once, and let the receiver, upon receiving a block of ℓ bits, take the majority of these ℓ bits. Because the bits are flipped independently, we can see that if ℓ = O(log t), where t is the communication complexity of the original protocol P (and λ is fixed), then there is a good probability that all the t bits will arrive correctly. This solution uses O(t log t) bits. Schulman presented transformations that result in an O(t) protocol P′ (either randomized [Schulman 1992] or deterministic [Schulman 1993]) that fails in simulating P with exponentially small probability in t (and again, λ is fixed). For extensions, see [Rajagopalan and Schulman 1994]. These results generalize results of [Shannon 1948] for one-way communication.