It is natural to expect that the more complex a concept is, the harder it is to learn. This paper improves this type of correlation for concepts that are represented by a class of circuits . It shows that if is learnable by an efficient algorithm that makes membership and equivalence queries, then there exists a set in EXP that cannot be computed by a circuit of type .

Previously, this was known for the larger complexity class EXP. We recall that a membership query for learning an unknown circuit C is of the type “What is the value of C on x?” An equivalence query is of the type “Is C=D?” (to which the teacher says YES or gives an input x on which C and D differ). The proof given in this paper uses efficient martingales of a certain type. The authors show that a learning algorithm for C can be transformed into a martingale that succeeds on C. On the other hand, it is known that there exist sets in EXP on which no martingale (of the type considered in this paper) succeeds.