CONSTRUCTING O(N LOG N) SIZE MONOTONE FORMULAS FOR THE KTH THRESHOLD FUNCTION OF N-BOOLEAN VARIABLES

In this paper we construct formulae for the kth elementary symmetric polynomial of n Boolean variables, using only conjunction and disjunction, which for fixed k are of size O(n log n), with the construction taking time polynomial in n. We also prove theorems involving n log n multiplied by (times) (polynomial in k) upper bounds on such formulae. Our methods involve solving the following combinatorial problem: for fixed k and any n construct a collection of r equals O(log n) function f//1,. . . ,f//r from left brace 1,. . . ,n right brace to left brace 1,. . . ,k right brace such that any subset of left brace 1,. . . ,n right brace of order k is mapped 1-1 to left brace 1,. . . ,k right brace by at least one f//i.