Bounded-depth, polynomial-size circuits for symmetric functions

Abstract

Let F= {f1, f2,...} be a family of symmetric Boolean functions, where fn has n Boolean variables, for each n ≥ 1. Let μF(n) be the minimum number of variables of fn that each have to be set to constant values so that the resulting function is a constant function. We show that the growth rate of μF(n) completely determines whether or not the family F is 'good', that is, can be realized by a family of constant-depth, polynomial-size circuits (with unbounded fan-in). Furthermore, if μF(n) ≤ (log n)k for some k, then the family F is good. However, if μF(n) ≥ nε{lunate} for some ε{lunate} > 0, then the family is not good. © 1985.