CaltechAUTHORS
  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 http://resolver.caltech.edu/CaltechAUTHORS:20120328-141319570

[img]
Preview
PDF - Published Version
See Usage Policy.

775Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120328-141319570

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/SFCS.1992.267778DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=267778PublisherUNSPECIFIED
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.
Funders:
Funding AgencyGrant Number
Office of Naval Research (ONR) Graduate Fellowship UNSPECIFIED
MIT Applied Mathematics Graduate FellowshipUNSPECIFIED
NSFCCR-8912586
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:http://resolver.caltech.edu/CaltechAUTHORS:20120328-141319570
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=267778&isnumber=6693
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29884
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:17 Apr 2012 21:25
Last Modified:26 Dec 2012 15:00

Repository Staff Only: item control page