Bounded-depth, polynomial-size circuits for symmetric functions (Q1063574)

Let \(\{f_ 1,f_ 2,...\}\) be a family of symmetric Boolean functions, where \(f_ n\) has n variables. For this family the minimum number of variables of \(f_ n\) is considered that have to be set to constant values so that the resulting function is a constant function. It is shown that the growth rate of this minimum completely determines whether or not the given family if ''good'', that is, can be realized by a family of constant-depth, polynomial-size circuits (with unbounded fan-in), and explicit growth rates, which define good respectively bad families, are given. The authors' results provide a unifying framework to show why the families of parity and majority functions are bad. (From the text).