Computational query complexity of SQ-learning
I've asked (myself) this question a while ago. At least for learning with respect to a specific distribution there is a fairly simple example of a concept class that is information theoretically SQ-learnable but is NP-hard to SQ learn. Let \phi  a binary encoding of a SAT instance and y be its lexicographically first satisfying assignment (or 0^n is the instance is unsatisfiable). Now let f(\phi) be a function that over one half of the domain is the MAJ(\phi) and over the second half of the domain equals PAR(y). Here MAJ is the majority function over variables which are set to 1 in the string \phi and PAR(y) is the parity function over variables which are set to 1 in the string y. Let F be the class of functions obtained in this way. To SQ learn F over the uniform distribution U one only needs to learn majorities (which is easy) to find \phi and then find y. On the other hand, it is fairly easy to reduce SAT to SQ learning of F (to any accuracy noticeably greater than 3/4) over the uniform distribution. The reason for this, naturally, is that parities are essentially "invisible" to SQs and hence it is necessary to solve SAT to learn F.