"Guided Inference of Nested Monotone Boolean Functions"

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

by Vetle I. Torvik and
Evangelos Triantaphyllou

Abstract:
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.