Boolean circuit size bounds on the majority function

Question

I am a bit lost in the literature. Is it known whether there is a $o(n \log n)$ size boolean circuit family for the majority function?

Answer 1

A binary full adder takes as input three bits $x,y,z$, and outputs two bits $a,b$ such that $x+y+z = 2a+b$.

Now suppose we are given $2^n$ bits $x_1,\ldots,x_{2^n}$. We compute as follows:

• $x_1 + x_2 = 2a_1 + b_1$.
• $b_1 + x_3 + x_4 = 2a_2 + b_2$. Thus $x_1 + x_2 + x_3 + x_4 = 2(a_1 + a_2) + b_2$.
• $b_2 + x_5 + x_6 = 2a_3 + b_3$. Thus $x_1 + \cdots + x_6 = 2(a_1 + a_2 + a_3) + b_3$.
• ...
• $b_{2^{n-1}-1} + x_{2^n-1} + x_{2^n} = 2a_{2^{n-1}} + b_{2^{n-1}}$. Thus $x_1 + \cdots + x_{2^n} = 2(a_1 + \cdots + a_{2^{n-1}}) + b_{2^{n-1}}$.

Using $O(2^n)$ gates, we computed $2^{n-1}$ bits $a_1,\ldots,a_{2^{n-1}}$ and a bit $b_{2^{n-1}}$ bits such that $$ x_1 + \cdots + x_{2^n} = 2(a_1 + \cdots + a_{2^{n-1}}) + b_{2^{n-1}}. $$ Thus $b^{2^{n-1}}$ is the LSB of the sum $x_1 + \cdots + x_{2^n}$, and the higher-order bits of the sum are just the sum $a_1 + \cdots + a_{2^{n-1}}$. In particular, the majority of $x_1,\ldots,x_{2^n}$ is the same as the majority of $a_1,\ldots,a_{2^{n-1}}$. This gives a recursive circuit for majority whose size satisfies the recurrence $$S(N) = S(N/2) + O(N), $$ whose solution is $S(N) = O(N)$.

If implemented carefully, the circuit size is roughly $5n$. Demenkov, Kojevnikov, Kulikov, and Yaroslavstev improved this to roughly $4.5n$ in their paper New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions.