Circuit complexity of symmetric Boolean functions in antichain basis
Olga Podolskaya · Discrete Mathematics and Applications · 2016
Abstract 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 The research is supported by the Russian Foundation for Basic Research, project 14–01–00598.