Circuit size for "at least n inputs are true"

Question

Say you have $m$ boolean inputs, and you are given a threshold $n$. You need to construct a boolean circuit that evaluates to true if at least $n$ of the inputs true. You may use AND, OR, NOT, or XOR gates (restricted to fan-in two, with arbitrary fan-out). Asymptotically how small can you make this circuit?

Any reasonably tight upper bound would be appreciated. I keep on thinking of ways to recursively construct such a circuit but I can't find anything good. Also, any results for any other reasonable basis of allowed gates would also be useful.

Answer 1

From S. Chaudhuri, J. Radhakrishnan. Deterministic Restrictions in Circuit Complexity:

Theorem 6.1: A circuit computing $T_k^n$ with $k \leq n^{1/3}$ has $\Omega(k^2(\ln n)/\ln k)$ gates

Where $T_k^n$ is the boolean function that has the value 1 iff at least $k$ of its inputs have the value 1 (threshold function).

Answer 2

We can get some sort of upper bound from some complexity inclusions.

$TC^{0}$ is the class of polynomially sized, constant depth boolean circuits where we also have a $MAJORITY$ gate of unbounded fan-in, so there's a size $1$ $TC^{0}$ circuit that computes the function you want (one $MAJ$ gate with all the inputs going to it).

$NC^{1}$ is the class of boolean circuits of polynomial size and $O(\log n)$ depth (but here we only have the normal gates). It is known that $TC^{0} \subseteq NC^{1}$, so at worst, you can compute $MAJ$ with a poly-size $O(\log n)$ depth circuit.

I suspect that as you only need $MAJ$, we can do better, but I haven't managed to get a good reference for this quite yet. Vollmer's "Introduction to Circuit Complexity" should have the reduction, but I don't have a copy available. It should also be a uniform reduction too (i.e. for an input of size $n$ we can efficiently produce the appropriate circuit).

This question on cstheory.SE might also have something useful to you in it, but it's pretty technical.

Answer 3

with $T_k^n$ a standard threshhold function defined as in Vors answer, $T_k^n$ is a symmetric function. thm 2.11.1 in Savage[1] gives a $O(n)$ size circuit.

[1] Models of Computation, John E Savage