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

*Proof*

Get *Theory of Computational Complexity, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.