Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

摘要

We study the following computational problem: for which values of k, the majority of n bits MAJ(n) can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk degrees MAJk. We observe that the minimum value of k for which there exists a MAJk degrees MAJk circuit that has high correlation with the majority of n bits is equal to Theta(n(1/2)). We then show that for a randomized MAJk degrees MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n(2/3 + o(1)). We show a worst case lower bound: if a MAJk degrees MAJk circuit computes the majority of n bits correctly on all inputs, then k = n(13/19 + o(1)).