Alladi Ramakrishnan Hall

Randomness Gives Little Advantage for Decision Tree Size

Yogesh Dahiya

IMSc

(Talk will be in-person. Zoom link for remote attendance --
zoom.us/j/92557905378
Meeting ID: 925 5790 5378
Passcode: 057022)

Nisan's classic result [SICOMP '91] shows that the randomized decision tree depth complexity of a total Boolean function is at least the cube of its deterministic decision tree depth complexity. However, the role of randomness on decision tree size complexity has not been explored. Adding to Nisan's result, we show that the logarithm of the deterministic decision tree size complexity of any total Boolean function is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, up to a polylogarithmic factor in the input dimension. Drawing an analogy, one can associate the depth of a decision tree with time complexity and its size with space complexity. Consequently, Nisan's result can be viewed as derandomizing time, while our result can be seen as derandomizing space. Our result has several implications for derandomizing query complexity in more generalized variants of decision trees. Specifically, we show that for total Boolean functions

1. The deterministic AND-OR query complexity is at most the fourth power of its randomized counterpart, ignoring a polylog n factor.

2. The deterministic AND (OR) query complexity is at most the cube of its randomized counterpart, ignoring a polylog n factor. This resolves an open question by Knop, Lovett, McGuire, and Yuan [SIGACT News '21].

Combining our result with Ehrenfeucht and Haussler's [Information and Computation'89] work, we also get 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 analogue of block sensitivity of a Boolean function that played a central role in Nisan's aforementioned result.

Joint work with Arkadev Chattopadhyay, Nikhil Mande, Jaikumar Radhakrishnan, and Swagato Sanyal.
To appear in STOC 2023.