2026-07-24T00:04:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9663 2024-03-06T10:44:39Z ddc:004 open_access

Depth Two Majority Circuits for Majority and List Expanders Amano, Kazuyuki Boolean function majority function constant depth circuit expander graph 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_{<= n-2} 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_{<= n-2} o MAJ_{n-2} circuit computing MAJ_n. Hence, our construction reveals that the use of a smaller fan-in 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 c-leftregular bipartite graph such that for a given d < c, every d-leftregular 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_{n-c} o MAJ_{n-c} circuit computing MAJ_n for a large constant c. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kazuyuki Amano 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.81 urn:nbn:de:0030-drops-96633 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.81 eng https://creativecommons.org/licenses/by/3.0/legalcode