A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
Uri Zwick · SIAM Journal on Computing · 1991
A simple, and easy-to-check, property of a symmetric boolean function is shown to imply a $4n - O(1)$ lower bound on the circuit complexity of the function over $U_2 = B_2 - \{ \oplus , \equiv \}$, the basis of unate dyadic boolean functions. Among the functions to which this lower bound applies are the modular functions ${\operatorname{MOD}}_k (n)$ for any fixed $k \geqq 3$ (${\operatorname{MOD}}_k (n)$ is the function which returns 1 if and only if $(\sum x_i )\bmod k = 0$). Finally, a $5n$ upper bound is obtained on the circuit complexity over $U_2 $ of the function ${\operatorname{MOD}}_4 (n)$.