Title: Tree tribes and lower bounds for switching lemmas,
Abstract: 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 every vertex is at a distance of at most $t$ from some
leaf, also called $t$-clipped decision trees. More specifically, we show the
following:
$\bullet$ If a boolean function $f$ can be expressed as a $t$-clipped
decision tree, then under the action of a random $p$-restriction $\rho$, the
probability that the smallest depth decision tree for $f|_{\rho}$ has depth
greater than $d$ is upper bounded by $(4p2^{t})^{d}$.
$\bullet$ For every $t$, there exists a function $g_{t}$ that can be
expressed as a $t$-clipped decision tree, such that under the action of a
random $p$-restriction $\rho$, the probability that the smallest depth decision
tree for $g_{t}|_{\rho}$ has depth greater than $d$ is lower bounded by
$(c_{0}p2^{t})^{d}$, for $0\leq p\leq c_{p}2^{-t}$ and $0\leq d\leq
c_{d}\frac{\log n}{2^{t}\log t}$, where $c_{0},c_{p},c_{d}$ are universal
constants.