Alain J. Mayer, Larry J. Stockmeyer
Theoretical Computer Science
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.
Alain J. Mayer, Larry J. Stockmeyer
Theoretical Computer Science
Richard J. Lipton, Larry J. Stockmeyer
STOC 1976
Larry J. Stockmeyer, Vijay V. Vazirani
Information Processing Letters
Arnold L. Rosenberg, Larry J. Stockmeyer, et al.
Theoretical Computer Science