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.
Paper
On the combinational complexity of certain symmetric Boolean functions
Abstract
A property of the truth table of a symmetric Boolean function is given from which one can infer a lower bound on the minimal number of 2-ary Boolean operations that are necessary to compute the function. For certain functions of n arguments, lower bounds between roughly 2 n and 5 n/2 can be obtained. In particular, for each m ≥ 3, a lower bound of 5 n/2 -O(1) is established for the function of n arguments that assumes the value 1 iff the number of arguments equal to 1 is a multiple of m. Fixing m = 4, this lower bound is the best possible to within an additive constant. © 1977 Springer-Verlag New York Inc.