We study the following computational problem: for which values of k, the majority of n bits MAJn 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 ∘ MAJk. We observe that the minimum value of k for which there exists a MAJk ∘ MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk ∘ MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3 + o(1). We show a worst case lower bound: if a MAJk ∘ MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19 + o(1).
Original language | English |
---|---|
Pages (from-to) | 956-986 |
Journal | Theory of Computing Systems |
Volume | 63 |
Issue number | 5 |
Early online date | 29 Nov 2018 |
DOIs | |
State | Published - Jul 2019 |
Externally published | Yes |
ID: 49820484