Bounds on the Size of Small Depth Circuits for Approximating Majority

Abstract

In this paper, we show that for every constant $0<\epsilon <1/2$ and for every constant $d\ge 2$, the minimum size of a depth $d$ Boolean circuit that $\epsilon$-approximates Majority function on $n$ variables is exp$(\Theta (n^{1/(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\ge 3$.

12 pages