Published November 1993
| Published
Book Section - Chapter
Open
Signal Propagation, with Application to a Lower Bound on the Depth of Noisy Formulas
- Creators
- Evans, Williams
-
Schulman, Leonard J.
Abstract
We study the decay of an information signal propagating through a series of noisy channels. We obtain exact bounds on such decay, and as a result provide a new lower bound on the depth of formulas with noisy components. This improves upon previous work of N. Pippenger and significantly decreases the gap between his lower bound and the classical upper bound of von Neumann. We also discuss connections between our work and the study of mixing rates of Markov chains.
Additional Information
© 1993 IEEE. Date of Current Version: 06 August 2002. Research supported in part by NSF grant CCR 92-01092. Research supported by an NSF postdoctoral fellowship. Thanks to N. Pippenger for helpful consultations.Attached Files
Published - EVAfocs93.pdf
Files
EVAfocs93.pdf
Files
(820.6 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:adaaabd495508823c23f2deeb4f21cd3
|
820.6 kB | Preview Download |
Additional details
- Eprint ID
- 29668
- Resolver ID
- CaltechAUTHORS:20120309-133211732
- CCR 92-01092
- NSF
- NSF Postdoctoral Fellowship
- Created
-
2012-03-12Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Series Name
- Annual Symposium on Foundations of Computer Science
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 4858027