Abstract
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].
3. The notion of rank of a Boolean function was defined in a classic work of Ehrenfeucht and Haussler [Information and Computation'89] in the context of learning theory, and is characterized by the logarithm of decision tree size up to a logarithmic factor in the input size. Our results confirm a recent conjecture (ignoring a polylog(n) factor) of Cornelissen, Mande and Patro [FSTTCS '22], that asserted the equivalence of randomized and deterministic analogs of rank, upto polynomial factors, for all total Boolean functions.
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.