next up previous
Next: Self-Delegation with Controlled Propagation Up: Sabbatical at MIT (1996-1998) Previous: Computational Indistinguishability - Algorithms

Computational Sample Complexity

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



Oded Goldreich
2003-07-30