From Exact Learning to Computing Boolean Functions and Back Again
This work addresses foundational theoretical issues in computational learning theory and Boolean function analysis, but it appears incremental as it focuses on establishing bounds rather than introducing new paradigms.
The paper tackles the problem of relating complexity measures for evaluating Boolean functions (certificate and decision tree complexity) to those for exact learning (teaching and extended teaching dimension), aiming to provide lower and upper bounds between these measures to connect exact learning and concept testing.
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.