Partially Symmetric Functions

Definition 2.5.1   A symmetric function is a Boolean function whose value depends only on the Hamming weight of the input.

Recall that the Hamming weight of a bit string is the number of 1's it has.

Consider the special class of $N$-bit Boolean functions $f$ such that $f(x) = 1$ for all inputs $x$ of Hamming weight $a$, and $f(x) = 0$ for all inputs $x$ of Hamming weight $b$. Without loss of generality assume $a < b$. We will attain a lower bound depending only on the parameters $a$ and $b$.

Theorem 2.5.1   Let $f$ be an $N$-bit Boolean function such that for some $a < b$, $\vert x\vert = a$ implies $f(x) = 1$, and $\vert x\vert = b$ implies $f(x) = 0$. Then

$$\Omega\left(\sqrt{\frac{(N-a)b}{(b-a)^{2}}}\right)$$

oracle queries are required to compute $f$ in the bounded error setting.

Like Lemma , this result allows us to easily attain lower bounds for many functions. In general, the closer $a$ and $b$ are to each other and to $N/2$ the better. We illustrate the particular success of Theorem in the case of symmetric functions in the following two sections, and with relatively less success in the case of non-trivial monotone graph properties in Section .