Expressing fact in polynomial size boolean expression

Question

If I have boolean variables a_1, a_2, .. , a_n. How can I express the fact that number of boolean variables which are set to true is bigger than some k, using polynomial size boolean expression? (Exponential is easy - just write newton(n,k) expressions).

Answer 1

Sort your booleans with any sorting network. Then just take (k+1)'th sorted bit, which gives you the result.

Since each of the sorting network's elements represents a pair of logical operations, you can interpret this network as logical expression. With good sorting network, this will give you an expression with O(N*log²(N)) operations.