1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.