ON EVALUATING BOOLEAN FUNCTIONS WITH UNRELIABLE TESTS
Claire Kenyon, Andrew Chi-Chih Yao · International Journal of Foundations of Computer Science · 1990
We consider the problem of evaluating a boolean function P(x 1 ,…,x n ), by asking queries of the form “x i =?”, 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+s P E+t P E), where s P is the maximal size of a minterm of P(x) and t P ‘is the maximal size of a maxterm. We also prove that if P is monotone, then any algorithm for evaluating P must ask Ω(s P E+t P E) queries for some input.