The Boolean Functions Computed by Random Boolean Formulas OR How to Grow the Right Function
Document Type
Article
Department
Mathematics (HMC)
Publication Date
12-2005
Abstract
We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such asValiant’s [J Algorithms 5 (1984), 363–366] hold. We completely characterize growth processes that use linear connectives and generalize Savický’s [Discrete Math 147 (1990), 95–103] analysis to characterize growth processes that use monotone connectives. Additionally, we obtain explicit bounds on the convergence rates of several growth processes, including the growth process studied in Savický. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 27, 490–519, 2005
Rights Information
© 2005 Wiley Periodicals, Inc.
Terms of Use & License Information
DOI
10.1002/rsa.20095
Recommended Citation
Brodsky, A. and Pippenger, N. (2005), The Boolean functions computed by random Boolean formulas or how to grow the right function. Random Structures & Algorithms, 27: 490–519. doi: 10.1002/rsa.20095