About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theoretical Computer Science
Paper
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.