Abstract
Let MAJ_n denote the Boolean majority function of n input variables. In this paper, we study the construction of depth two circuits computing MAJ_n where each gate in a circuit computes MAJ_m for m < n.
We first give an explicit construction of depth two MAJ_{floor[n/2]+2} o MAJ_{<= n2} circuits computing MAJ_n for every n >= 7 such that n congruent 3 (mod 4) where MAJ_m and MAJ_{<= m} denote the majority gates that take m and at most m distinct inputs, respectively. A graph theoretic argument developed by Kulikov and Podolskii (STACS '17, Article No. 49) shows that there is no MAJ_{<= n2} o MAJ_{n2} circuit computing MAJ_n. Hence, our construction reveals that the use of a smaller fanin gates at the bottom level is essential for the existence of such a circuit. Some computational results are also provided.
We then show that the construction of depth two MAJ_m o MAJ_m circuits computing MAJ_n for m<n can be translated into the construction of a newly introduced version of bipartite expander graphs which we call a list expander. Intuitively, a list expander is a cleftregular bipartite graph such that for a given d < c, every dleftregular subgraph of the original graph has a certain expansion property. We formalize this connection and verify that, with high probability, a random bipartite graph is a list expander of certain parameters. However, the parameters obtained are not sufficient to give us a MAJ_{nc} o MAJ_{nc} circuit computing MAJ_n for a large constant c.
BibTeX  Entry
@InProceedings{amano:LIPIcs:2018:9663,
author = {Kazuyuki Amano},
title = {{Depth Two Majority Circuits for Majority and List Expanders}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {81:181:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9663},
URN = {urn:nbn:de:0030drops96633},
doi = {10.4230/LIPIcs.MFCS.2018.81},
annote = {Keywords: Boolean function, majority function, constant depth circuit, expander graph}
}
Keywords: 

Boolean function, majority function, constant depth circuit, expander graph 
Collection: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 
Issue Date: 

2018 
Date of publication: 

27.08.2018 