Next: Self-Delegation with Controlled Propagation
Up: Sabbatical at MIT (1996-1998)
Previous: Computational Indistinguishability - Algorithms
Using standard intractability assumptions,
this work proves that there exist concept classes that
possess arbitrary sized gaps between their standard
(information-theoretic) sample complexity
and their computational sample complexity
(i.e., the size of the sample required by probabilistic
polynomial-time learning algorithms).
The same holds also with respect to learning from membership queries
and learning from noisy examples.
Comments:
Authored by S. Decatur, O. Goldreich and D. Ron. Appeared in
- 10th COLT, pp. 130-142, 1997.
- SIAM Jour. on
Comp., Vol. 29,
Nr. 3, pages 854-879, 1999.
Oded Goldreich
2003-07-30