Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring @math bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires @math knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips @math bits, our algorithm sends @math bits in expectation and succeeds with high probability in @math . It does so without any @math knowledge of @math . Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown.
For @math bits to be transmitted from Alice to Bob, Shannon @cite_6 proposes an error correcting code of size @math that yields correct communication over a noisy channel with probability @math . At first glance, this may appear to solve our problem. But consider an interactive protocol with communication complexity @math , where Alice sends one bit, then Bob sends back one bit, and so forth where the value of each bit sent depends on the previous bits received . Two problems arise. First, using block codewords is not efficient; to achieve a small error probability, dummy'' bits may be added to each bit prior to encoding, but this results in a superlinear blowup in overhead. Second, due to the interactivity, an error that occurs in the past can ruin all computation that comes after it. Thus, error correcting codes fall short when dealing with interactive protocols.
@cite_6
2041404167
Scientific knowledge grows at a phenomenal pace--but few books have had as lasting an impact or played as important a role in our modern world as The Mathematical Theory of Communication, published originally as a paper on communication theory more than fifty years ago. Republished in book form shortly thereafter, it has since gone through four hardcover and sixteen paperback printings. It is a revolutionary work, astounding in its foresight and contemporaneity. The University of Illinois Press is pleased and honored to issue this commemorative reprinting of a classic.