Evans, Williams and Schulman, Leonard J. (1993) Signal Propagation, with Application to a Lower Bound on the Depth of Noisy Formulas. In: 34th Annual Symposium on Foundations of Computer Science Proceedings. Annual Symposium on Foundations of Computer Science . IEEE Computer Society Press , Los Alamitos, CA, pp. 594-603. ISBN 0-8186-4370-6 http://resolver.caltech.edu/CaltechAUTHORS:20120309-133211732
![[img]](http://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 801Kb |
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120309-133211732
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.
| Item Type: | Book Section | ||||||
|---|---|---|---|---|---|---|---|
| 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. | ||||||
| Funders: |
| ||||||
| Other Numbering System: |
| ||||||
| Record Number: | CaltechAUTHORS:20120309-133211732 | ||||||
| Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20120309-133211732 | ||||||
| Related URLs: | |||||||
| Official Citation: | Evans, W.; Schulman, L.J.; , "Signal propagation, with application to a lower bound on the depth of noisy formulas," Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on , vol., no., pp.594-603, 3-5 Nov 1993 doi: 10.1109/SFCS.1993.366827 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=366827&isnumber=8405 | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 29668 | ||||||
| Collection: | CaltechAUTHORS | ||||||
| Deposited By: | Ruth Sustaita | ||||||
| Deposited On: | 12 Mar 2012 18:43 | ||||||
| Last Modified: | 26 Dec 2012 14:56 |
Repository Staff Only: item control page
