Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-049 | 9th April 2006 00:00

The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions


Authors: Guy Wolfovitz
Publication: 18th April 2006 15:39
Downloads: 3067


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.


Comment #1 to TR06-049 | 13th June 2023 10:19

Some upper bounds aren't correct

Authors: Ryan Williams
Accepted on: 13th June 2023 10:19


The upper bounds claimed for general symmetric functions (Lemma 3, Theorem 2, Corollary 1) are unfortunately incorrect. As of June 2023, it appears to still be open (for example) whether MAJORITY has depth-3 circuits of size $2^{O(sqrt{n})}$ or not, and whether MAJORITY requires depth-3 bottom fan-in k circuits of size $2^{\Omega(n \log k)/k}$. (However, it does appear to be true that $EXACT_{n/k}$ has a depth-3 bottom fan-in $k$ circuit of size $2^{O(n/k)}$, as claimed in the abstract.)

I am leaving a comment because this preprint often appears in web searches for circuit upper bounds on symmetric functions, and it does not seem well-known that these problems are still open.

The source of the problem was highlighted in footnote 2 of "The Composition Complexity of Majority" (CCC 2022, https://drops.dagstuhl.de/opus/volltexte/2022/16581/). Here I reproduce that footnote in its entirety:

"Briefly, in the notation of [this preprint], it requires that $kn/c < n$, and so $k < c$, but $c$ then takes on all the values of $n, n/2, n/3, \ldots, 1$ and $k \approx \sqrt{n}$. The third author thanks Srikanth Srinivasan [2] who informed him
about this gap in the proof."

ISSN 1433-8092 | Imprint