A Caltech Library Service

Information Theory and Noisy Computation

Evans, William S. and Schulman, Leonard J. (1995) Information Theory and Noisy Computation. In: Proceedings: 1995 IEEE International Symposium on Information Theory. IEEE , Piscataway, NJ, p. 456. ISBN 0-7803-2453-6.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We report on two types of results. The first is a study of the rate of decay of information carried by a signal which is being propagated over a noisy channel. The second is a series of lower bounds on the depth, size, and component reliability of noisy logic circuits which are required to compute some function reliably. The arguments used for the circuit results are information-theoretic, and in particular, the signal decay result is essential to the depth lower bound. Our first result can be viewed as a quantified version of the data processing lemma, for the case of Boolean random variables.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 1995 IEEE. Date of Current Version: 06 August 2002. Supported by a Canadian International Fellowship and NSF grant CCR 92-01092. Supported in part by an NSF Postdoctoral Fellowship.
Funding AgencyGrant Number
Canadian International FellowshipUNSPECIFIED
NSFCCR 92-01092
NSF Postdoctoral FellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number 5280203
Record Number:CaltechAUTHORS:20120216-114451513
Persistent URL:
Official Citation:Evans, W.S.; Schulman, L.J.; , "Information theory and noisy computation," Information Theory, 1995. Proceedings., 1995 IEEE International Symposium on , vol., no., pp.456, 17-22 Sep 1995 doi: 10.1109/ISIT.1995.550443 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29341
Deposited By: Ruth Sustaita
Deposited On:16 Feb 2012 21:11
Last Modified:09 Nov 2021 17:06

Repository Staff Only: item control page