Tree Tribes and Lower Bounds for Switching Lemmas
Jenish C. Mehta · arXiv (Cornell University) · 2017
Let f be a Boolean function on n variables, rho a random p-restriction that independently keeps each variable unset (or free) with probability p and otherwise uniformly sets it to 0 or 1, and DT_{depth}(f) denote the depth of the smallest depth decision tree for f. Let R_d(f|rho) be the resilience of f to rho for depth d, defined as R_d(f|rho)=Pr_{rho = d]. If d >> pn, all functions have resilience close to 0 since less than d variables would remain unset with high probability. For d =(c_0 p2^t)^d, for 0 <= p <= c_p 2^-t and 0 <= d <= c_d * (log n)/(2^t * t log t) (where c_0,c_p,c_d are universal constants). As a result, for sufficiently large n and small d, this gives a hierarchy of functions with strictly increasing resilience, and covers the entire region between the two extremes where functions have resilience (close to) 0 or 1.