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 http://resolver.caltech.edu/CaltechAUTHORS:20120216-114451513
![[img]](http://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 130Kb |
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120216-114451513
Abstract
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 | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 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. | ||||||||
| Funders: |
| ||||||||
| Other Numbering System: |
| ||||||||
| Record Number: | CaltechAUTHORS:20120216-114451513 | ||||||||
| Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20120216-114451513 | ||||||||
| Related URLs: | |||||||||
| 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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=550443&isnumber=11520 | ||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||
| ID Code: | 29341 | ||||||||
| Collection: | CaltechAUTHORS | ||||||||
| Deposited By: | Ruth Sustaita | ||||||||
| Deposited On: | 16 Feb 2012 21:11 | ||||||||
| Last Modified: | 26 Dec 2012 14:51 |
Repository Staff Only: item control page
