Bounds on the Size of Small Depth Circuits for Approximating Majority

2009/01/31 by Amano, Kazuyuki
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.0902.0047

Abstract

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^1/(2d-2))). 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.

Related

• Computing Majority by Constant Depth Majority Circuits with Low Fan-in\n Gates
• An average-case depth hierarchy theorem for Boolean circuits
• A Duality Between Depth-Three Formulas and Approximation by Depth-Two
• Top-Down Lower Bounds for Depth-Four Circuits
• The composition complexity of majority