Abstract <p>Suppose there is a function <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(f\)</EquationSource>  </InlineEquation> from some class of functions <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(F\)</EquationSource>  </InlineEquation>, where either the values of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(f\)</EquationSource>  </InlineEquation> 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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(F\)</EquationSource>  </InlineEquation> is the class of Boolean functions, and any a priori knowledge about <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(f\)</EquationSource>  </InlineEquation> is not known, the learner has to query all input vectors to fully identify <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(f\)</EquationSource>  </InlineEquation>. However, if it is known that <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(f\)</EquationSource>  </InlineEquation> is monotone, then certain inferences can be made: if <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(f\left( \alpha \right) = 1\)</EquationSource>  </InlineEquation>, then <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(f\left( \beta \right) = 1\)</EquationSource>  </InlineEquation> for all <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\beta \)</EquationSource>  </InlineEquation> such that <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\alpha \prec \beta \)</EquationSource>  </InlineEquation>; and if <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(f\left( \alpha \right) = 0\)</EquationSource>  </InlineEquation>, then <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(f\left( \beta \right) = 0\)</EquationSource>  </InlineEquation> for all <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\beta \)</EquationSource>  </InlineEquation> such that <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\beta \prec \alpha \)</EquationSource>  </InlineEquation>. 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 <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(n\)</EquationSource>  </InlineEquation> variables – is given by the number of elements of the two middle layers of the binary hypercube: <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\varphi \left( n \right) = \left( {\begin{array}{{20}{c}} n \\ {\left[ {n{\text{/2}}} \right]} \end{array}} \right) + \left( {\begin{array}{{20}{c}} n \\ {\left[ {n{\text{/2}}} \right] + 1} \end{array}} \right)\)</EquationSource>  </InlineEquation>. In this paper, we introduce a new subclass of Boolean functions called <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(k\)</EquationSource>  </InlineEquation>-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.</p>

Recognition of k-Distance Monotone Boolean Functions

期刊论文
出版模式：

开放获取
发表日期：

2025年12月1日

查看全文

Hasmik Sahakyan,
Levon Aslanyan

摘要

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\left( \alpha \right) = 1\) , then \(f\left( \beta \right) = 1\) for all \(\beta \) such that \(\alpha \prec \beta \) ; and if \(f\left( \alpha \right) = 0\) , then \(f\left( \beta \right) = 0\) for all \(\beta \) such that \(\beta \prec \alpha \) . 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: \(\varphi \left( n \right) = \left( {\begin{array}{*{20}{c}} n \\ {\left[ {n{\text{/2}}} \right]} \end{array}} \right) + \left( {\begin{array}{*{20}{c}} n \\ {\left[ {n{\text{/2}}} \right] + 1} \end{array}} \right)\) . 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.