Randomized versus Deterministic Decision Tree Size

Chattopadhyay, Arkadev, Dahiya, Yogesh, Mande, Nikhil S ORCID: 0000-0002-9520-7340, Radhakrishnan, Jaikumar and Sanyal, Swagato (2023) Randomized versus Deterministic Decision Tree Size In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023-6-20 - 2023-6-23, Orlando, Florida, USA.

Text REF_STOC_2023.pdf - Author Accepted Manuscript Download (631kB) | Preview

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. 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.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	Boolean functions, derandomization, query complexity
Divisions:	Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	12 Apr 2023 08:59
Last Modified:	22 May 2026 16:22
DOI:	10.1145/3564246.3585199
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3169453
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.