Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 1992 | Published
Book Section - Chapter Open

Communication on noisy channels: a coding theorem for computation

Abstract

Communication is critical to distributed computing, parallel computing, or any situation in which automata interact-hence its significance as a resource in computation. In view of the likelihood of errors occurring in a lengthy interaction, it is desirable to incorporate this possibility in the model of communication. The author relates the noisy channel and the standard (noise less channel) complexities of a communication problem by establishing a `two-way' or interactive analogue of Shanon's coding theorem: every noiseless channel protocol can be simulated by a private-coin noisy channel protocol whose time bound is proportional to the original (noiseless) time bound and inversely proportional to the capacity of the channel, while the protocol errs with vanishing probability. The method involves simulating the original protocol while implementing a hierarchical system of progress checks which ensure that errors of any magnitude in the simulation are, with high probability, rapidly eliminated.

Additional Information

© 1992 IEEE. Support for this research was provided by an ONR graduate fellowship, an MIT Applied Mathematics graduate fellowship, and grants NSF 8912586 CCR and AFOSR 89-0271. I thank Mike Sipser, whose encouragement of my work on this project, and supervision of its progress, have been invaluable. Further I thank Peter Elias for much advice and assistance. For consultations and comments thanks also to Dan Abramovich, Robert Gallager, Wayne Goddard, Mauricio Karchmer, Dan Kleitman, Mike Klugerman and Andrew Sutherland.

Attached Files

Published - SCHUfocs92.pdf

Files

SCHUfocs92.pdf
Files (793.8 kB)
Name Size Download all
md5:96bf5f6e55db84f09f7802f31aca0069
793.8 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 24, 2023