Circuit complexity of symmetric Boolean functions in antichain basis

We study the circuit complexity of Boolean functions in an infinite basis consisting of all characteristic functions of antichains over the Boolean cube. For an arbitrary symmetric function we obtain the exact value of its circuit complexity in this basis. In particular, we prove that the circuit complexities of the parity function and the majority function of $n$ variables for all integers $n\geqslant1$ in this basis are $\lfloor \frac{n+1}{2} \rfloor$ and $\left\lfloor \frac{n}{2} \right \rfloor +1$ respectively. For the maximum circuit complexity of $n$-variable Boolean functions in this basis, we show that its order of growth is equal to $n.$ \hspace{12cm} \linebreak

The research is supported by the Russian Foundation for Basic Research, project 14–01–00598.