ON BOOLEAN DECISION TREES WITH FAULTY NODES

We consider the problem of computing with faulty components in the con text of the Boolean decision tree model, in which cost is measured by the number of input bits queried, and the responses to queries are fau lty with a fixed probability. We show that if f can be represented in k-DNF form and in j-CNF form, then O(n log(min(k, j)/q)) queries suffi ce to compute f with error probability less than q, where n is the num ber of input bits. (C) 1994 John Wiley & Sons, Inc.