"Guided Inference of Nested Monotone Boolean Functions"

Information Sciences, No. 151, pp. 171-200, 2003.

by Vetle I. Torvik and Evangelos Triantaphyllou

This paper addresses the problem of minimizing the average query complexity of inferring a pair of nested monotone Boolean functions defined on {0,1}n, using a pair of oracles. It is shown that this problem is equivalent to inferring a single monotone Boolean function defined on {0,1}n, when access to the two oracles is unrestricted. The improvement factor due to the nestedness assumption is shown to be greater for problems with a smaller number of variables, n. For unrestricted oracles, the average query complexity is reduced by 20% for n = 1, and levels off at about 5% for larger values of n (greater than 9). This is a dramatic improvement considering the fact that the average query complexity is exponential in n. Two common examples of restricted oracles, namely sequential oracles and a single three valued oracles, are also analyzed. It is shown that the framework for unrestricted inference is easily modified for use with restricted oracles.

Key Words:
Nested monotone Boolean functions, membership queries, guided inference, partially ordered sets (posets), query selection criterion, average query complexity.

Download this paper as a PDF file. (Size = 486 KB)

Visit Dr. Triantaphyllou's homepage.