Decision Trees with Boolean Threshold Queries

摘要

We investigate decision trees in which one is allowed to query threshold functions of subsets of variables. We are mainly interested in the case where only queries of AND and OR are allowed. This model is a generalization of the classical descision tree model. Its complexity (depth) is related to the parallel time that is required to compute Boolean functions in certain CRCW PRAM machines with only one cell of constant size. It is also related to the computation using Ethernet channel. We prove a tight lower bound of θ(k log(n/k)) for the required depth of a decision tree for the threshold-k function. As a corollary of the method we also prove a tight lower bound for the "direct sum" problem of computing simultaneously k copies of threshold-2 in this model. Next, the size complexity is considered. A relation to depth-three circuits is established and a lower bound is proven. Finally the relation between randomized, nondeterminism, and determinism is also investigated, we show separation results between these models.