Learning Concepts Definable in First-Order Logic with Counting
  We study classification problems over relational background structures for
hypotheses that are defined using logics with counting. The aim of this paper
is to find learning algorithms running in time sublinear in the size of the
background structure. We show that hypotheses defined by FOCN(P)-formulas over
structures of polylogarithmic degree can be learned in sublinear time.
Furthermore, we prove that for structures of unbounded degree there is no
sublinear learning algorithm for first-order formulas.
