Abstract Suppose there is a function f from some class of functions F, where either the values of f at some input points are known or the learner can query the function (possibly with noise). The goal is for the learner to recover the function exactly or approximately—a classic problem in learning theory. If F is the class of Boolean functions, and any a priori knowledge about f is not known, the learner has to query all input vectors to fully identify f. However, if it is known that f is monotone, then certain inferences can be made: if f () = 1, then f () = 1 for all such that ; and if f () = 0, then f () = 0 for all such that. The Shannon complexity of this recognition task—defined as the minimum number of queries required in the worst case for an arbitrary monotone Boolean function on n variables – is given by the number of elements of the two middle layers of the binary hypercube: (n) = (array{*{20c} n \\ {n{/2} } array}) + (array{*{20c} n \\ {n{/2} + 1} array}). In this paper, we introduce a new subclass of Boolean functions called k -distance monotone, relaxing the strict monotonicity requirement. We investigate the recognition problem for this class and determine the query-based recognition complexity for 2-distance monotone functions.
Sahakyan et al. (Mon,) studied this question.