A Circuit of Depth Two with Limited Input Branching for Majority Functions / Yu. A. Kombarov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2018. № 5. P. 58-60 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 196-198].

It is shown that a majority Boolean function of n variables can be computed by a depth-2 circuit consisting of majority gates with fan-in n-2 (for each odd n greater than 5).

Key words: Boolean circuits, Boolean functions, majority function, bounded fan-in.

№ 5/2018