On Boolean Decision Trees with Faulty Nodes

Claire Kenyon - Valerie King

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 if f can be represented in k-DNF form and in j-CNF form, then $O(n\log (\min (k,j)/q))$ queries suffice to compute f with error probability less than q, where n is the number of input bits.

About this document ...

On Boolean Decision Trees with Faulty Nodes

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -dir /users/algo/kenyon/WWW/Publis/ -split 0 boolean-abstract.tex.

The translation was initiated by Claire Kenyon on 3/19/1998

Footnotes

...Kenyon

Current address: LIP ENS-Lyon, 46 Allée d'Italie, 69364 Lyon Cedex 07, France. Part of this work was done while the author was visiting NECI, Princeton, and at LIENS in Paris.

...King

Current address: Computer Science Department, University of Victoria, BC, Canada V8W 3P2. This work was done while the author was at NECI, Princeton.