patternMinor
Circuit size for "at least n inputs are true"
Viewed 0 times
inputsaresizetrueforleastcircuit
Problem
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.
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.
Solution
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).
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).
Context
StackExchange Computer Science Q#3291, answer score: 8
Revisions (0)
No revisions yet.