Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 1993 | Published
Book Section - Chapter Open

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


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 (820.6 kB)
Name Size Download all
820.6 kB Preview Download

Additional details

August 20, 2023
January 13, 2024