Learning of Bounded-Weight Boolean Functions
A. V. Bystrygova · Moscow University Mathematics Bulletin · 2021
Abstract The complexity of exact learning of bounded-weight Boolean functions is considered in the paper separately using four types of queries: membership queries, equivalence queries, extended equivalence queries, and comparation queries. The values of the complexity for the first three types are obtained for all classes of functions at consideration. Upper and lower bounds of the complexity for comparation queries being of the same order are presented. Moreover, the exact value of the complexity of learning upper bounded-weight Boolean functions with the help of comparation queries is obtained.