A p-random restriction is a random partial input obtained by independently leaving each input variable unset with probability p setting them to either 0,1 with (1-p)/2 each.
Criticality of a boolean function f is the inverse of the probability p at which the decision tree depth t of a random restriction of f goes down exponentially in t.The ground breaking work of Hastad’s Switching lemma is a bound on criticality of CNFs and DNFs. Rossman defined the notion of criticality and showed its connection to average case lower bounds, fourier tail bounds, and decision tree size.
In this talk we will see implications of bounds on criticality to average case lower bounds, Fourier tail bounds and decision tree size and an Entropy Switching lemma for DNFs due to Rossman.
