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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training,
learning paths, books, interactive tutorials, and more.