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
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120328-141319570
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|
|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.|
|Other Numbering System:|
|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.|
|Deposited By:||Tony Diaz|
|Deposited On:||17 Apr 2012 21:25|
|Last Modified:||26 Dec 2012 15:00|
Repository Staff Only: item control page