On boolean decision trees with faulty nodes
Claire Kenyon, Valerie Jean King · Random Structures and Algorithms · 1994
Abstract We consider the problem of computing with faulty components in the context of the Boolean decision tree model, in which cost is measured by the number of input bits queried, and the responses to queries are faulty with a fixed probability. We show that iffcan be represented ink‐DNF form and inj‐CNF form, thenO(nlog(min(k, j)/q)) queries suffice to computefwith error probability less thanq, wherenis the number of input bits. © 1994 John Wiley & Sons, Inc.