  The goal of the paper is to relate complexity measures associated with the
evaluation of Boolean functions (certificate complexity, decision tree
complexity) and learning dimensions used to characterize exact learning
(teaching dimension, extended teaching dimension). The high level motivation is
to discover non-trivial relations between exact learning of an unknown concept
and testing whether an unknown concept is part of a concept class or not.
Concretely, the goal is to provide lower and upper bounds of complexity
measures for one problem type in terms of the other.
