A circuit of depth two with limited input branching for voting function
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2018), pp. 58-60
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
We show that majority Boolean function of $n$ variables can be computed by a depth-2 circuit consisting of majority gates with fan-in $n-2$ (for every odd $n$ greater than 5).
[1] Kulikov A.S., Podolskii V.V., “Computing majority by constant depth majority circuits with low fan-in gates”, 34th Symp. on Theoretical Aspects of Computer Science (STACS 2017), 2017, 49:1–49:14 | MR
[2] Engels C., Grag M., Makino K., Rao A., “On expressing majority as majority of majorities”, Electronic Colloquium on Computational Complexity, TR17-174
[3] Ugolnikov A.B., Klassy Posta, Izd-vo TsPI pri mekh.-mat. f-te MGU, M., 2008