<p>Kaveh's answer provides an answer do the question as you have stated it (and this is the usual proof for showing that $\mathsf{TC}^0$ is contained in $\mathsf{NC}^1$). But I was thinking that you might actually have intended to ask a slightly a different question. Namely for an explicit polynomial size <em>monotone</em> formula for majority.</p>

<p>Since majority is monotone we know it can be computed by a monotone formula. There are two known constructions polynomial size monotone formulas, namely the two you mention, Valiant's probabilistic construction and the construction via sorting networks. As far as I know we have no simpler deterministic construction than that provided by sorting networks.</p>

<p>Related to this is also the following. It turns out that majority can be computed by formulas that consists of <em>only</em> $\mathsf{MAJ}_3$ gates (and no constants!). Valiant's probabilistic construction can be adapted to give such formulas of $O(\log(n))$ depth. However here we known of no deterministic construction. In particular the sorting networks are not suitable for this (technical reason: they would provide all the threshold functions and only the majority function can be computed at all by $\mathsf{MAJ}_3$ gates). There is however recent progress on this question given in the paper <a href="http://dx.doi.org/10.1007/978-3-642-40084-1_11"> Efficient Multiparty Protocols via Log-Depth Threshold Formulae</a> by Cohen et al. Here such formulas are construction based on standard complexity-theoretic or cryptographic assumptions.</p>

CC BY-SA 3.0
2014-03-06T11:53:25.007Z
2014-03-06T11:53:25.007Z
Kristoffer Arnsfelt Hansen
<p>Computing restricted threshold gate ($\sum_i x_i \geq k$) is essentially sorting input bits.</p>

<p>If you can sort the bits then it is easy to compare the result to $k$ and 
compute restricted threshold.</p>

<p>On the other hand, assume that we have an circuits to compute restricted threshold. 
We can do a parallel search to find the number of ones in the input and 
output the sorted list.</p>

<p>These preserve circuit depth. So if you come up with a new $\mathsf{NC^1}$ circuit to compute the restricted threshold then it will give a depth $O(\lg n)$ sorting circuit.
So if we come up with a simple argument for showing majority is in $\mathsf{NC^1}$ 
you have found a simple depth-$O(\lg n)$ sorting circuit 
(other than the one based on AKS sorting network).</p>

<p>Note that it is easy to implement the restricted threshold using majority by adding new 1 and 0 inputs to the majority gate.</p>

<hr>

<p>Previously this answer claimed that it can be done using divide and conquer and the fact that binary addition is in $\mathsf{AC^0}$. That only shows that majority is in $\mathsf{AC^1}$ and $\mathsf{NC^2}$ since we have unbounded fan-in gates in the binary addition if we do it directly. However it can be done with a bit more work.</p>

<p>We have to use the trick called <em>three-for-two</em> to remain in depth $O(\lg n)$. </p>

<blockquote>
  <p><strong>three-for-two binary addition:</strong><br>
  given three binary numbers $a,b,c$ we can compute two binary numbers $x,y$ such that
  $a+b+c = x+y$.</p>
</blockquote>

<p>Another method is to use signed digit representation of integers where addition can be done in depth $O(1)$ and fan-in 2. (The idea is to use the flexibility that a number can be represented in more than one way to make sure that carries do not propagate).</p>

<p>See section 4 and exercise 4 in</p>

<ul>
<li>David Mix Barrington and Alexis Maciel, "<a href="http://www.cse.buffalo.edu/~regan/cse682/lectureA06.pdf">Advanced Course on Computational Complexity</a>", lecture 6, IAS/PCMI, 2000.</li>
</ul>

CC BY-SA 3.0
2014-03-06T04:05:56.163Z
It seems to me both of these give deterministic sorting circuits of depth $O(\lg n)$ (and might also lead to a simpler deterministic sorting networks of depth $O(\lg n)$).
Kaveh
CC BY-SA 3.0
2014-03-06T00:04:21.077Z
2014-03-06T15:01:04.727Z
2014-03-06T15:01:04.727Z
Kaveh
<p>The proof (due to Miller and Preparata, 1975) that any symmetric function can be computed by circuits over {AND,OR,NOT} in logarithmic depth can be found, e.g., in <a href="https://eccc.weizmann.ac.il/static/books/The_Complexity_of_Boolean_Functions/" rel="nofollow noreferrer">Complexity of Boolean Functions</a> by Ingo Wegener (Theorem 4.1, page 76). The corresponding circuit has linear size. And since the depth is logarithmic it can be turned to a formula of polynomial size. The proof is elementary and gives an explicit construction. Basically, it shows how to compute the binary representation of the sum of <span class="math-container">$n$</span> input bits in logarithmic depth (having this sum it is straightforward to compute majority).</p>
<p>An alternative proof is given by Brodal and Husfeldt: <a href="http://www.brics.dk/RS/96/1/BRICS-RS-96-1.pdf" rel="nofollow noreferrer">A Communication Complexity Proof
that Symmetric Functions have Logarithmic Depth</a>. Again, the proof is elementary and provides an explicit construction.</p>

CC BY-SA 4.0
2014-12-08T10:20:35.063Z
2024-02-05T19:21:02.670Z
2024-02-05T19:21:02.670Z
Alexander S. Kulikov
<p>Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i &gt; n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I mean not relying on the probabilistic method like Valiant 84 did or on sorting networks; preferably providing an explicit, straightforward construction of the circuit): </p>

<p>$f$ can be computed by a family of circuits of $O(\log(n))$ depth, poly(n) size, where the gates consists of NOT gates, 2-input OR gates, and 2-input AND gates.</p>

CC BY-SA 3.0
2014-03-06T16:12:41.883Z
This might be of interest:  [Igor Sergeev, Upper bounds for the formula size of the majority function](http://arxiv.org/abs/1208.3874); also [here](http://old.kpfu.ru/journals/izv_vuz/index.php?id=4&idm=18&num=5)  he announces slightly better upper bounds. However, if you ask about just *circuits* (not *formulas*) then, as Igor reminded me, *every* symmetric boolean function (not just majority) has a circuit of depth $O(\log n)$ and size $O(n)$: just compute the sum of $1$s, and realize a boolean function of $\log_2n$ variables. For majority, this latter function is a comparison with $n/2$.
Stasys
CC BY-SA 3.0
2014-03-06T17:15:18.757Z
@Stasys, and computing the number of ones is essentially sorting the bits.
Kaveh
<cc.complexity-theory><circuit-complexity><boolean-functions><circuit-families><circuit-depth>
Circuit complexity of Majority function
matthon
# Circuit complexity of Majority function

(Asked by: username_0 on 2014-03-05)

Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum\_{i = 1}^n x\_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I mean not relying on the probabilistic method like Valiant 84 did or on sorting networks; preferably providing an explicit, straightforward construction of the circuit):

$f$ can be computed by a family of circuits of $O(\log(n))$ depth, poly(n) size, where the gates consists of NOT gates, 2-input OR gates, and 2-input AND gates.

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, circuit-families, circuit-depth
> **Comments:**
> **username_1**: This might be of interest:  [Igor Sergeev, Upper bounds for the formula size of the majority function](http://arxiv.org/abs/1208.3874); also [here](http://old.kpfu.ru/journals/izv_vuz/index.php?id=4&idm=18&num=5)  he announces slightly better upper bounds. However, if you ask about just *circuits* (not *formulas*) then, as Igor reminded me, *every* symmetric boolean function (not just majority) has a circuit of depth $O(\log n)$ and size $O(n)$: just compute the sum of $1$s, and realize a boolean function of $\log_2n$ variables. For majority, this latter function is a comparison with $n/2$.  
> **username_2**: @Stasys, and computing the number of ones is essentially sorting the bits.  

---

## 3 answers

### Answer by username_3 on 2014-03-06. Score: 11

Kaveh's answer provides an answer do the question as you have stated it (and this is the usual proof for showing that $\mathsf{TC}^0$ is contained in $\mathsf{NC}^1$). But I was thinking that you might actually have intended to ask a slightly a different question. Namely for an explicit polynomial size *monotone* formula for majority.

Since majority is monotone we know it can be computed by a monotone formula. There are two known constructions polynomial size monotone formulas, namely the two you mention, Valiant's probabilistic construction and the construction via sorting networks. As far as I know we have no simpler deterministic construction than that provided by sorting networks.

Related to this is also the following. It turns out that majority can be computed by formulas that consists of *only* $\mathsf{MAJ}\_3$ gates (and no constants!). Valiant's probabilistic construction can be adapted to give such formulas of $O(\log(n))$ depth. However here we known of no deterministic construction. In particular the sorting networks are not suitable for this (technical reason: they would provide all the threshold functions and only the majority function can be computed at all by $\mathsf{MAJ}\_3$ gates). There is however recent progress on this question given in the paper  [Efficient Multiparty Protocols via Log-Depth Threshold Formulae](http://dx.doi.org/10.1007/978-3-642-40084-1_11) by Cohen et al. Here such formulas are construction based on standard complexity-theoretic or cryptographic assumptions.


---

### Answer by username_2 on 2014-03-06. Score: 11

Computing restricted threshold gate ($\sum\_i x\_i \geq k$) is essentially sorting input bits.

If you can sort the bits then it is easy to compare the result to $k$ and
compute restricted threshold.

On the other hand, assume that we have an circuits to compute restricted threshold.
We can do a parallel search to find the number of ones in the input and
output the sorted list.

These preserve circuit depth. So if you come up with a new $\mathsf{NC^1}$ circuit to compute the restricted threshold then it will give a depth $O(\lg n)$ sorting circuit.
So if we come up with a simple argument for showing majority is in $\mathsf{NC^1}$
you have found a simple depth-$O(\lg n)$ sorting circuit
(other than the one based on AKS sorting network).

Note that it is easy to implement the restricted threshold using majority by adding new 1 and 0 inputs to the majority gate.

---

Previously this answer claimed that it can be done using divide and conquer and the fact that binary addition is in $\mathsf{AC^0}$. That only shows that majority is in $\mathsf{AC^1}$ and $\mathsf{NC^2}$ since we have unbounded fan-in gates in the binary addition if we do it directly. However it can be done with a bit more work.

We have to use the trick called *three-for-two* to remain in depth $O(\lg n)$.

> **three-for-two binary addition:**  
> given three binary numbers $a,b,c$ we can compute two binary numbers $x,y$ such that
> $a+b+c = x+y$.

Another method is to use signed digit representation of integers where addition can be done in depth $O(1)$ and fan-in 2. (The idea is to use the flexibility that a number can be represented in more than one way to make sure that carries do not propagate).

See section 4 and exercise 4 in

* David Mix Barrington and Alexis Maciel, "[Advanced Course on Computational Complexity](http://www.cse.buffalo.edu/~regan/cse682/lectureA06.pdf)", lecture 6, IAS/PCMI, 2000.

> **Comments:**
> **username_2**: It seems to me both of these give deterministic sorting circuits of depth $O(\lg n)$ (and might also lead to a simpler deterministic sorting networks of depth $O(\lg n)$).  

---

### Answer by username_4 on 2014-12-08. Score: 9

The proof (due to Miller and Preparata, 1975) that any symmetric function can be computed by circuits over {AND,OR,NOT} in logarithmic depth can be found, e.g., in [Complexity of Boolean Functions](https://eccc.weizmann.ac.il/static/books/The_Complexity_of_Boolean_Functions/) by Ingo Wegener (Theorem 4.1, page 76). The corresponding circuit has linear size. And since the depth is logarithmic it can be turned to a formula of polynomial size. The proof is elementary and gives an explicit construction. Basically, it shows how to compute the binary representation of the sum of $n$ input bits in logarithmic depth (having this sum it is straightforward to compute majority).

An alternative proof is given by Brodal and Husfeldt: [A Communication Complexity Proof
that Symmetric Functions have Logarithmic Depth](http://www.brics.dk/RS/96/1/BRICS-RS-96-1.pdf). Again, the proof is elementary and provides an explicit construction.


---

