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 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. Our result has the following consequences:-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.-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].-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.-Combined with the above-mentioned work of Ehrenfeucht and Haussler, our result implies that the class of functions computable by randomized decision trees of polynomial size, is PAC-learnable in quasi-polynomial time. To obtain our main result on decision tree size, we use as an intermediate measure the∗block number∗of a Boolean function, studied first by Kulkarni and Tal [CJTCS'16], 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.

• View at Publisher
• View at Scopus

Free Full Text ( Final Version , 736kb )