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 queries suffice to
compute f with error probability less than q, where n is the
number of input bits.
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