The Boolean Functions Computed by Random Boolean Formulas OR How to Grow the Right Function

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow
Alex Brodsky, University of Toronto

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.

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