The Boolean Functions Computed by Random Boolean Formulas OR How to Grow the Right Function
Nicholas J. Pippenger, Alex Brodsky · Scholarship - Claremont (Claremont Colleges) · 2005
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