Randomized versus Deterministic Decision Tree Size
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal · 2023
A classic result of Nisan [SICOMP ’91] states that the deterministic decision tree *depth* complexity of every total Boolean function is at most the cube of 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.