Identification of Partial Disjunction, Parity, and Threshold Functions

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify "efficiently" a Boolean function g out of F by asking for the value of g at chosen inputs, where "efficiency" is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are respectively obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries. Key words: Complexity of Boolean functions, attribute-efficient learning, randomization. 3 A preliminary version of this paper has been published as extended abstract in the Proceedings of the EuroCOLT '97, LNAI 1208, 171-184, 1997. 33 Supported in part by DFG grant We 1066/8-1. 1 Introduction Exact concept learning of Boolean concepts (or Bo..