Part 3. Mathematical models

Complexity of learning linear boolean functions

A. V. Bistrigova


Abstract: The exact learning of a linear Boolean function of $k$ relevant variables is considered in this work. Here we obtain the complexity of learning such functions for $k < 4$ and upper bounds for other values of $k$.

Keywords: linear Boolean functions, exact learning.