An Application of Codes to Attribute-Efficient Learning

摘要

We design asymptotically optimal query strategies for the class of parity functions which contain at most k essential variables. The number of questions askd is at most twice the number asked by an optimal strategy. The strategy presented is even non-adaptive. For fixed k, the number of questions is optimal up to additive constants. Our results improve upon results by uehara, Tsuchida and Wegener[6].