Abstract
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.
One of the consequences of our result is that the randomized and decision query complexity of every total function in the AND (OR) decision tree model are also polynomially related. This confirms a recent conjecture made by Knop, Lovett, McGuire and Yuan (SIGACT News'21, STOC'21).
(Joint work with Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan and Swagato Sanyal)