Products and help bits in decision trees

We investigate two problems concerning the complexity of evaluating a function f at k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth bound d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best decision tree algorithm of depth d is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth d algorithms are all correct is at most p^k, which is the trivial lower bound. We show that if we replace the depth d restriction by “expected depth d”, then this result fails. In the help-bit problem, we are permitted to ask k-1 arbitrary binary questions about the k-tuple of inputs. For each possible k-1-tuple of answers to these queries we will have a k-tuple of decision trees which are supposed to correctly compute all functions on k-tuples that are consistent with the particular answers. The complexity here is the maximum depth of any of the trees in the algorithm. We show that for all k sufficiently large, this complexity is equal to deg^s(f) which is the minimum degree of a multivariate polynomial whose sign is equal to f. Finally, we give a brief discussion of these problems in the context of other complexity models