On the complexity of monotone circuits for threshold symmetric Boolean functions

Abstract The complexity of implementation of a threshold symmetric n -place Boolean function with threshold k = O (1) via circuits over the basis {∨, ∧} is shown not to exceed 2 log 2 k ⋅ n + o ( n ). Moreover, the complexity of a threshold-2 function is proved to be 2 n + Θ ( $\begin{array}{} \sqrt n \end{array} $ ), and the complexity of a threshold-3 function is shown to be 3 n + O (log n ), the corresponding lower bounds are put forward.