Bounds on the Size of Small Depth Circuits for Approximating Majority

الأصل · EN

In this paper, we show that for every constant 0 < ε< 1/2 and for every constant d ≥ 2, the minimum size of a depth d Boolean circuit that ε-approximates Majority function on n variables is exp(Θ(n¹/⁽²ᵈ⁻²⁾)). The lower bound for every d ≥ 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 ≥ 3.