A Caltech Library Service

Communication on noisy channels: a coding theorem for computation

Schulman, Leonard J. (1992) Communication on noisy channels: a coding theorem for computation. In: 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, pp. 724-733. ISBN 0-8186-2900-2.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
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.
Funding AgencyGrant Number
Office of Naval Research (ONR) Graduate FellowshipUNSPECIFIED
MIT Applied Mathematics Graduate FellowshipUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)89-0271
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number4498953
Record Number:CaltechAUTHORS:20120328-141319570
Persistent URL:
Official Citation:Schulman, L.J.; , "Communication on noisy channels: a coding theorem for computation ," Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on , vol., no., pp.724-733, 24-27 Oct 1992 doi: 10.1109/SFCS.1992.267778 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29884
Deposited By: Tony Diaz
Deposited On:17 Apr 2012 21:25
Last Modified:09 Nov 2021 19:31

Repository Staff Only: item control page