Bounds on the Size of Small Depth Circuits for Approximating Majority

Kazuyuki Amano

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 functi…