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 $(4p{2}^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}p{2}^t{)}^d$, for $0\le p\le c_p{2}^{-t}$ and $0\le d\le c_d\frac{\log n}{2^t\log t}$, where $c_0,c_p,c_d$ are universal constants.