Decision Trees and Data Structures

Eyal Kushilevitz, Noam NisanCambridge 1996 · DOI · OpenAlex

Abstract

One of the simplest models of computation is the decision tree model. In this model we are concerned with computing a function f: {0, 1}m → {0, 1} by using queries. Each query is given by specifying a function q on {0, l}m taken from some fixed family Q of allowed queries (the queries need not be Boolean). The answer given for the query is simply the value of q(x1, …, xm). The algorithm is completely adaptive, that is the i-th query asked may depend in an arbitrary manner on the answers received for the first i − 1 queries. The only wayto gain information about the input x is through these queries. The algorithm can therefore be described as a labeled tree, whose nodes are labeled by queries q ∈ Q, the outgoing edges of each node are labeled by the possible values of q(x1, …, xm), and the leaves are labeled by output values. Each sequence of answers describes a path in the tree to a node that is either the next query or the value of the output. In Figure 9.1 a decision tree is shown that computes (on inputs x1, …, x4) whether at least three of the input bits are 1s. It uses a family of queries Q consisting of all disjunctions of input variables and conjunctions of input variables.
BibTeX
@inproceedings{kushilevitz1996decision,
  author = {Eyal Kushilevitz and Noam Nisan},
  title = {{Decision Trees and Data Structures}},
  booktitle = {Cambridge},
  year = {1996},
  doi = {10.1017/cbo9780511574948.010},
}

Loading related content...

Figure