Title

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

Terms of Use for work posted in Scholarship@Claremont.