Depth Two Majority Circuits for Majority and List Expanders.

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_{ = 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

Keywords:

• Discrete mathematics
• Electronic circuit
• Computer science
• Combinatorics
• graph theoretic
• Majority function
• Graph
• high probability
• Expander graph
• Congruence (geometry)
• Bipartite graph

• Correction
• Source
• Cite
• Save
• Machine Reading By IdeaReader