Circuit complexity of Majority function

Question

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.

Answer 1

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 by Cohen et al. Here such formulas are construction based on standard complexity-theoretic or cryptographic assumptions.

Answer 2

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", lecture 6, IAS/PCMI, 2000.

Answer 3

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 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. Again, the proof is elementary and provides an explicit construction.