Randomized versus Deterministic Decision Tree Size

A classic result of Nisan [SICOMP '91] states that the deterministic decision tree depth complexity of every total Boolean function is at most cubic in its randomized decision tree depth complexity. The question whether randomness helps in significantly reducing the size of decision trees appears not to have been addressed. We show that the logarithm of the deterministic decision tree size complexity of every total Boolean function on n input variables is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, ignoring a polylogarithmic factor in the input size. Our result has the following consequences: 1. The deterministic AND-OR query complexity of a total Boolean function is at most the fourth power of its randomized AND-OR query complexity, ignoring a polylog(n) factor. 2. The deterministic AND (OR) query complexity of a total Boolean function is at most the cube of its randomized AND (OR) query complexity, ignoring a polylog(n) factor. This answers a recent open question posed by Knop, Lovett, McGuire and Yuan [SIGACT News '21]. To obtain our main result on decision tree size, we use the notion of block number of a Boolean function, which can be thought of as a counting analog of block sensitivity of a Boolean function that played a central role in Nisan's result mentioned above. Based on joint work with Arkadev Chattopadhyay, Yogesh Dahiya, Jaikumar Radhakrishnan and Swagato Sanyal.