Theory of Computational Complexity, 2nd Edition

To establish a general lower bound for the randomized decision tree complexity of weakly symmetric functions, let us first show an inequality about weakly symmetric functions.

Lemma 5.38

If f is a weakly symmetric Boolean function, then

where n is the number of variables of f.

Proof

Let Γ be the group of permutations on variables of f that witnesses the weak symmetry of f. Consider the number

This number is independent of the choices of x and y, because for any x, y, and z, we can map one-to-one into in the following way: Choose such that . Then, for each σ with , we have .That is, the mapping meets our requirement. Similarly, we can map one-to-one into .

Let . Then, for ...