Header menu link for other important links
X
Power of Decision Trees with Monotone Queries
, Amireddy P., Jayasurya S.
Published in Springer Science and Business Media Deutschland GmbH
2020
Volume: 12273 LNCS
   
Pages: 287 - 298
Abstract
In this paper we initiate study of the computational power of adaptive and non-adaptive monotone decision trees - decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree height (or size) can be viewed as a measure of non-monotonicity of a given Boolean function. We also study the restriction of the model by restricting (in terms of circuit complexity) the monotone functions that can be queried at each node. This naturally leads to complexity classes of the form for any circuit complexity class, where the height of the tree is, and the query functions can be computed by monotone circuits in class. In the above context, we prove the following characterizations and bounds. We show that the decision tree height can be exactly characterized (both in the adaptive and non-adaptive versions of the model) in terms of the alternation of a function (defined as the maximum number of times that the function value changes, in any chain in the Boolean lattice). We also characterize the non-adaptive decision tree height with a natural generalization of certification complexity of a function. We also show upper bounds and characterizations for non-deterministic and randomized variants of the monotone decision trees in terms of. We show that when contains monotone circuits for the threshold functions. For, we show that any function in can be computed by a sub-linear height monotone decision tree with queries having monotone circuits.To explore the logarithmic height case - we show that for any f (on n bits) in, and for any constant, there is an circuit for f with negation gates. In contrast, it can be derived from[14] that for every with, and for every, any circuit computing it with negations will need at least depth. En route the main results, as a tool, we study the monotone variant of the decision list model, and prove corresponding characterizations in terms of and also derive as a consequence that if has appropriate closure properties (where is defined similar to but for decision lists). © 2020, Springer Nature Switzerland AG.