# On parallel attribute-efficient learning

**Journal of computer and system sciences**(0022-0000). Vol. 67 (2003), 1, p. 46-62.

[Artikel, refereegranskad vetenskaplig]

This paper continues our earlier work on (non)adaptive attribute-efficient learning. We consider exact learning of Boolean functions of n variables by membership queries, assuming that at most r variables are relevant. The learner works in consecutive rounds, such that the set of simultaneous queries in every round may depend on all information gained so far. For deterministic learning of specific monotone functions we prove that any strategy that uses an optimal query number needs a number of rounds linear in r in the worst case. Furthermore we make some progress regarding the constant factors in nearly query-optimal strategies. In contrast to the limitations of deterministic strategies, there is a randomized strategy that learns monotone functions in a logarithmic number of rounds. Actually this result holds in more general function classes. The second part of the paper addresses the computational complexity of parallel learning of arbitrary Boolean functions with r relevant variables. We obtain several strategies which use a constant number of rounds and polynomially many computations.

**Nyckelord: **learning by queries, monotone Boolean functions, relevant variables, limits of parallelization, binary codes, randomization, auxiliary computation, special assignment families

Denna post skapades 2006-09-25. Senast ändrad 2015-02-11.

CPL Pubid: 1744