Bounds on the Size of Small Depth Circuits for Approximating Majority

In this paper, we show that for every constant $0<ϵ<1\mathrm{/}2$ and for every constant $d\ge 2$, the minimum size of a depth $d$ Boolean circuit that $ϵ$-approximates Majority function on $n$ variables is exp$(\mathrm{\Theta }(n^{1\mathrm{/}(2d-2)}))$. The lower bound for every $d\ge 2$ and the upper bound for $d=2$ have been previously shown by O’Donnell and Wimmer [ICALP’07], and the contribution of this paper is to give a matching upper bound for $d \geq 3$.