12
$\begingroup$

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

$n=9$, $m=7$: enter image description here

$\endgroup$
  • 3
    $\begingroup$ Just to clarify: the leaves are variables, or do you also allow constants or negative literals? $\endgroup$ – Emil Jeřábek Jan 10 '15 at 14:11
  • $\begingroup$ What does the function $m(n)$ measure? The smallest possible such $m$? $\endgroup$ – Francisco Mota Jan 10 '15 at 19:08
  • 2
    $\begingroup$ Thank you for the feedback! I've simplified the question as well as added two examples. $\endgroup$ – Alexander S. Kulikov Jan 11 '15 at 10:58
  • 1
    $\begingroup$ @Alexander: this could be somehow related. $\endgroup$ – Stasys Jan 11 '15 at 11:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jan 11 '15 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.