Decision Trees and Data Structures
Lists
Only you see this
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...