On Evaluating Boolean Functions with Unreliable Tests
Report ID: TR-263-90Author: Yao, Andrew / Kenyon, Claire
Date: 1990-04-00
Pages: 11
Download Formats: |PDF|
Abstract:
We consider the problem of evaluating a boolean function P(x1, ..., xn) by asking queries of the form "xi =?," and receiving answers which may not always be truthful. Assuming that the total number of lies does not exceed E, we present an algorithm with cost O(n+sPE+tPE), where sP is the maximal size of a minterm of P(x) and tP is the maximal size of a maxterm. We also prove that if P is monotone, then any algorithm for evaluating P must ask omega(sPE + tPE) queries for some input.