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.
https://resolver.caltech.edu/CaltechAUTHORS:20120328-141319570
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)  Preview |
|
PDF
- Published Version
See Usage Policy.
793kB |
Use this Persistent URL to link to this item: https://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: | |
---|
ORCID: | |
---|
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 Agency | Grant Number |
---|
Office of Naval Research (ONR) Graduate Fellowship | UNSPECIFIED | MIT Applied Mathematics Graduate Fellowship | UNSPECIFIED | NSF | CCR-8912586 | Air Force Office of Scientific Research (AFOSR) | 89-0271 |
|
---|
Other Numbering System: | Other Numbering System Name | Other Numbering System ID |
---|
INSPEC Accession Number | 4498953 |
|
---|
DOI: | 10.1109/SFCS.1992.267778 |
---|
Record Number: | CaltechAUTHORS:20120328-141319570 |
---|
Persistent URL: | https://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: | 09 Nov 2021 19:31 |
---|
Repository Staff Only: item control page