Bounds on the Size of Small Depth Circuits for Approximating Majority
Abstract
Description
In this paper, we show that for every constant $0 < ε< 1/2$ and for every constant $d \geq 2$, the minimum size of a depth $d$ Boolean circuit that $ε$-approximates Majority function on $n$ variables is exp$(Θ(n^{1/(2d-2)}))$. The lower bound for every $d \geq 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$.
12 pages
12 pages