Upper Estimate of Realization Complexity of Linear Functions in a Basis Consisting of Multi-Input Elements / Yu. A. Kombarov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2015. № 5. P. 47-50
[Moscow Univ. Mech. Bulletin. Vol. 72, N 2, 2017. P. 226-229].
The paper is focused on realization of parity functions
by circuits in the basis U_\infty . This basis contains all functions of the form
(x_1^{\sigma_1} \& \ldots \& x_k^{\sigma_k})^{\beta }.
A method of construction of circuits for a parity function of n variables with
the complexity \lfloor (7n-4) / 3 \rfloor is described. This improves the previously known upper bound
of U_\infty -complexity of parity functions that was \lceil (5n - 1)/2 \rceil .
The minimality of constructed circuits is verified for very small n (for n < 7).
