A Caltech Library Service

Signal Propagation, with Application to a Lower Bound on the Depth of Noisy Formulas

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.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
Related URLs:
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.
Funding AgencyGrant Number
NSFCCR 92-01092
NSF Postdoctoral FellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number4858027
Record Number:CaltechAUTHORS:20120309-133211732
Persistent URL:
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29668
Deposited By: Ruth Sustaita
Deposited On:12 Mar 2012 18:43
Last Modified:26 Dec 2012 14:56

Repository Staff Only: item control page