Tree tribes and lower bounds for switching lemmas

Jenish C. Mehta

We show tight upper and lower bounds for switching lemmas obtained by the action of random $p$-restrictions on boolean functions that can be expressed as decision trees in which ev…