**Authors: Scott E. Decatur, Oded Goldreich, Dana Ron**

**Source: ***SIAM Journal on Computing* Vol. **29**, No. 3,
1999, 854-879.

**Abstract.**
In a variety of PAC learning models, a trade-off between time
and information seems
to exist: with unlimited time, a small amount of information suffices,
but with time restrictions,
more information sometimes seems to be required. In addition,
it has long been known that there
are concept classes that can be learned in the absence of
computational restrictions, but (under
standard cryptographic assumptions) cannot be learned in polynomial time
(regardless of sample size). Yet, these results do not answer the question
of whether there are classes for which learning
from a small set of examples is computationally infeasible, but becomes
feasible when the learner
has access to (polynomially) more examples.

To address this question, we introduce a new measure of learning complexity
called *computational sample complexity* that represents the number
of examples sufficient for *polynomial time* learning
with respect to a fixed distribution. We then show concept classes that
(under similar
cryptographic assumptions) possess arbitrarily sized gaps between their standard
(information-theoretic) sample complexity and their computational sample
complexity. We also demonstrate such gaps for learning from membership
queries and learning from noisy examples.

©Copyright 1999, Society for Industrial and Applied Mathematics.