Bounds on the Size of Small Depth Circuits for Approximating Majority
| dc.creator | Amano, Kazuyuki | |
| dc.date | 2009-01-31 | |
| dc.date.accessioned | 2026-07-07T12:36:49Z | |
| dc.date.available | 2026-07-07T12:36:49Z | |
| dc.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$. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/0902.0047 | |
| dc.identifier | http://arxiv.org/abs/0902.0047 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/218226 | |
| dc.subject | Computational Complexity | |
| dc.title | Bounds on the Size of Small Depth Circuits for Approximating Majority | |
| dc.type | text |