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.