<p>Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c&lt;1$? Such a formula contains $m+1$ gates and $m^2$ leaves so $c$ must be at least $1/2$. I assume that the leaves can only be labeled by variables (without negations), but it would be also interesting to know the answer if we allow also negated variables and constants.</p>

<p>Two examples of such formulas are given below.</p>

<p>$n=7$, $m=5$: </p>

<p><img src="https://i.sstatic.net/5QnvG.png" alt="enter image description here"></p>

<p>$n=9$, $m=7$:
<img src="https://i.sstatic.net/uYhVa.png" alt="enter image description here"></p>

CC BY-SA 3.0
2015-01-10T14:11:04.463Z
Just to clarify: the leaves are variables, or do you also allow constants or negative literals?
Emil Jeřábek
CC BY-SA 3.0
2015-01-10T19:08:14.300Z
What does the function $m(n)$ measure? The smallest possible such $m$?
Francisco Mota
CC BY-SA 3.0
2015-01-10T19:13:20.080Z
I'm slightly unclear about your model, see Emil's comment.  Moreover, did you want to exclude the construction achieving arbitrarily large $m = kn$ by applying majority to a $k$-times repeat of the $n$ inputs, then repeating this subformula $m$ times?
András Salamon
CC BY-SA 3.0
2015-01-11T10:58:38.183Z
Thank you for the feedback! I've simplified the question as well as added two examples.
Alexander S. Kulikov
CC BY-SA 3.0
2015-01-11T11:33:47.223Z
@Alexander: [this](http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/thr.pdf) could be somehow related.
Stasys
CC BY-SA 3.0
2015-01-11T14:34:58.463Z
While this is likely not relevant for the asymptotic growth of $m$, I note there is a parity constraint: $\mathrm{MAJ}_m$-circuits with $m$ odd compute self-dual monotone functions, hence they can only express $\mathrm{MAJ}_n$ for $n$ odd.
Emil Jeřábek
CC BY-SA 3.0
2015-01-12T13:45:56.340Z
Thank you, Stasys! Emil, yes, it does not seem to help estimating the asymptotic growth of $m$.
Alexander S. Kulikov
<cc.complexity-theory><circuit-complexity><boolean-functions><boolean-formulas><circuit-depth>
Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2
Alexander S. Kulikov
# Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2

(Asked by: username_0 on 2015-01-10)

Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and $m^2$ leaves so $c$ must be at least $1/2$. I assume that the leaves can only be labeled by variables (without negations), but it would be also interesting to know the answer if we allow also negated variables and constants.

Two examples of such formulas are given below.

$n=7$, $m=5$:

![enter image description here](https://i.sstatic.net/5QnvG.png)

$n=9$, $m=7$:
![enter image description here](https://i.sstatic.net/uYhVa.png)

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, boolean-formulas, circuit-depth
> **Comments:**
> **username_1**: Just to clarify: the leaves are variables, or do you also allow constants or negative literals?  
> **username_2**: What does the function $m(n)$ measure? The smallest possible such $m$?  
> **username_3**: I'm slightly unclear about your model, see Emil's comment.  Moreover, did you want to exclude the construction achieving arbitrarily large $m = kn$ by applying majority to a $k$-times repeat of the $n$ inputs, then repeating this subformula $m$ times?  
> **username_0**: Thank you for the feedback! I've simplified the question as well as added two examples.  
> **username_4**: @Alexander: [this](http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/thr.pdf) could be somehow related.  
> **username_1**: While this is likely not relevant for the asymptotic growth of $m$, I note there is a parity constraint: $\mathrm{MAJ}_m$-circuits with $m$ odd compute self-dual monotone functions, hence they can only express $\mathrm{MAJ}_n$ for $n$ odd.  
> **username_0**: Thank you, Stasys! Emil, yes, it does not seem to help estimating the asymptotic growth of $m$.  

---

## 0 answers

