Upper bounds on the depth of symmetric Boolean functions

A new method for implementing the counting function with Boolean circuits is proposed. It is based on modular arithmetic and allows us to derive new upper bounds for the depth of the majority function of n variables: 3.34log2 n over the basis B 2 of all binary Boolean functions and 4.87log2 n over the standard basis B 0 = {∧, ∨, -}. As a consequence, the depth of the multiplication of n-digit binary numbers does not exceed 4.34log2 n and 5.87log2 n over the bases B 2 and B 0, respectively. The depth of implementation of an arbitrary symmetric Boolean function of n variables is shown to obey the bounds 3.34log2 n and 4.88log2 n over the same bases. © 2013 Allerton Press, Inc.