Identification of partial disjunction, parity, and threshold functions

Let F be a class of functions obtained by replacing some inputs of a Boolea n function of a fixed type with some constants. The problem considered in t his paper, which is called attribute efficient learning, is to identify "ef ficiently" a Boolean function g out of F by asking for the value of g at ch osen inputs, where "efficiency" is measured in terms of the number of essen tial variables. We study the query complexity of attribute-efficient learni ng for three function classes that are, respectively, obtained from disjunc tion, parity, and threshold functions. In many cases, we obtain almost opti mal upper and lower bound on the number of queries. (C) 2000 Elsevier Scien ce B.V. All rights reserved.