Paper Info
Title
Guided inference of nested monotone Boolean functions
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. Here, nested refers to the case when one of the functions is always greater than or equal to the other function. It is shown that the nested case is equivalent to inferring the single function case defined on {0, 1}n+1 when access to the two oracles is unrestricted. Two common examples of restricted oracles, namely sequential oracles and a single three-valued oracle, are also analyzed. The most efficient known approach to minimizing the average query complexity in inferring a single monotone Boolean function is based on a query selection criterion. It is shown that the selection criterion approach is easily modified for use with restricted oracles. Several real world examples illustrate the necessity and sufficiency of the nested monotone Boolean function model. Extensive computational results indicate that the nestedness assumption reduces the average query complexity by a few percent. This is a dramatic improvement considering the fact that this complexity is exponential in n.
Year
DOI
Venue
2003
10.1016/S0020-0255(03)00062-8
Inf. Sci.
Keywords
Field
DocType
query selection criteria,nested case,membership queries,single monotone boolean function,restricted oracle,guided inference,partially ordered sets posets,average query complexity,single three-valued oracle,efficient known approach,average query complexity.,single function case,selection criterion approach,nested monotone boolean function,query selection criterion,nested monotone boolean functions,partially ordered set
Discrete mathematics,Combinatorics,Exponential function,Inference,Necessity and sufficiency,Oracle,Selection criterion,Complexity index,Monotone boolean function,Mathematics,Boolean conjunctive query
Journal
Volume
ISSN
Citations 
151,
0020-0255
3
PageRank 
References 
Authors
0.70
8
2
Name
Order
Citations
PageRank
Vetle I. Torvik143027.15
Evangelos Triantaphyllou230946.53