Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-049 | 9th April 2006 00:00

The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions

RSS-Feed




TR06-049
Authors: Guy Wolfovitz
Publication: 18th April 2006 15:39
Downloads: 1317
Keywords: 


Abstract:

We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin $k$ which computes the Boolean function $EXACT_{n/(k+1)}^{n}$, has at least $(1+1/k)^{n+\O(\log n)}$ gates. We show that this lower bound is tight, by generalizing a known upper bound on the size of depth-3 circuits with bottom fanin 2, computing symmetric Boolean functions.



ISSN 1433-8092 | Imprint